Maximum Sum Problem

You are given a number N that can be broken into three parts N / 2, N / 3, and N / 4 (considering only integer parts). Each number obtained in this process can be divided further recursively. Your task is to find the maximum sum that can be obtained by summing up the divided parts together.

Note:

The maximum sum may be obtained without dividing N also.

For example :

N = 12 breaking N into three parts will give 6, 4, and 3 which gives us the sum = 13. Further breaking 6, 4, and 3 into other parts will give us a sum less than or equal to 6, 4, and 3 respectively. Therefore, the maximum answer will be 13.

Input format :

The first line of input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains a single integer N.

Output format :

 For each test case, in a separate line, print a single integer which is the maximum sum. 

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

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

Time Limit : 1 sec