Assuming that there are N pillars, and we need to put onto the pillars, a bunch of balls, i.e., numbered 1, 2, 3, 4, 5, ..., in increasing order such that on the same pillar, the sum of the numbers of any 2 adjacent balls is a square number. Calculate the maximum number of balls that can be placed on the N pillars. You may put the ball on any pillar, but no balls can be skipped. The process stops once you cannot not place a ball. For example, on 2 pillars, A and B, you can place 1 on pillar A, 2 on pillar B. Then 3 will have to go on pillar A (1+3=4 is a square), and finally 4 cannot be placed (as 4+4=8, and 2+4=6 are neither squares), and we are done (ending up with 3 placed balls). Input A number of test cases (≤ 1000), one per line, each with N (0 < N < 1000000000). Output For each test case, output the total number of balls on one line. Sample Input 1 2 Sample Output 1 3