Maximum Sum Problem Statement

Given an integer N, your task is to recursively break it into three integer parts: N / 2, N / 3, and N / 4. You need to compute the maximum sum possible by dividing the number further. Note that the maximum sum may also be achieved without dividing N.

Input:

The first line contains an integer T, representing the number of test cases.
Each of the following lines contains a single integer N.

Output:

For each test case, output in a separate line the maximum obtainable sum.

Example:

Input:

2
12
2

Output:

13
2

Explanation:

For N = 12, breaking it into 6, 4, and 3 gives a sum of 13, which is greater than any further possible division.
For N = 2, dividing results in 0, 0, and 0. The maximum sum is therefore N itself, which is 2.

Constraints:

• 1 <= T <= 5
• 1 <= N <= 3000

Note: There is no need to print anything within the function; just return the calculated result for each test case.