There are N students standing in a queue ready for parade . The students are being put into formation by Ujjwal Sir . Ujjwal Sir can divide the queue into any number of groups , each group having atleast one student each . Swayam Sir then chooses any group among the ones made by Ujjwal Sir to give T-shirts . After Swayam Sir chooses a group , only that group stays back and the rest of the students disperse . Now the number of T-shirts given to the group by Swayam Sir will be equal to the square of the index of the group chosen by him. The remaining students again form a queue and are again divided into groups by Ujjwal Sir and again Swayam Sir distributes T-shirt according to the algorithm given above. This continues until only one student is left . Now Swayam Sir wants to distribute maximum number of T-shirts for his football team, while Ujjwal Sir makes the divisions such that the least number of T-shirts are distributed because he wants to optimize the budget. Assuming that both take their decisions optimally, You have to tell the minimum number of T-shirts that will be distributed .
Input
The first line contains a single integer T, denoting the number of test cases. Each of the subsequent lines contains a single integer N.
Output
For each test case, print a single integer denoting the minimum number of T-shirts that will be distributed.
Constraints
1 <= T <= 100
2 <= N <= 1018
For First Test Case :
When N=3, Ujjwal sir will divide the queue in 2 groups having 2 at first index and 1 at second index. After this Swayam sir will select first index such that he gain 1 T-shirt according to rule (12=1)
In next turn, 2 people left in the queue ,Ujjwal sir divide the queue in two groups having 1 at first index and 1 at second index.After this, Swayam sir will select second index such that he gains 4 T-shirts according to rule (22=4)
Since only 1 student is left in the queue hence the game ends.So, total number of T-shirts gained by Swayam sir is (4+1)=5.
