Consider a N * N * N lattice. One corner is at (0, 0, 0) and the opposite one is at (N, N, N). How many lattice points are visible from corner at (0, 0, 0)? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.

Input

The first line contains the number of test cases T. The next T lines contain an integer N.

Output

Output T lines, one corresponding to each test case.

Sample

Input:
3
1
2
5
Sample Output:
7
19
175

Constraints

1 <= N <= 1000000