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 cube (k3 for positive integer k). 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. Input A number of of inputs (≤ 1000), each with N (0 < N ≤ 2000000). Output For each input, output the total number of balls on one line. Sample Input 1 2 8 Sample Output 1 2 15