Let's call a matrix A[3 x 3] Dinostratus if all its nine elements are different positive integer numbers and each its element a_i,j (where 1 ≤ i,j ≤ 3) is a multiple of its neighbors a_i-1,j, a_i-1,j-1 and a_i,j-1 (if they exist). In other words the following conditions hold:

• a_i,j = X · a_i-1,j for some positive integer X (if i ≥ 2)
• a_i,j = Y · a_i,j-1 for some positive integer Y (if j ≥ 2)
• a_i,j = Z · a_i-1,j-1 for some positive integer Z (if i,j ≥ 2)

For example the matrices

are Dinostratus. And the following matrices are not:

Let's define the element a_3,3 of a Dinostratus matrix A[3 x 3] as a base number. Given a base number, find out how many different Dinostratus matices exist. Two matrices A and B are different if there are such indexes i, j that a_i,j ≠ b_i,j.

Input

Input file consists of several test cases. Input file starts with a line containing an integer T (T ≤ 500), which is the number of test cases. The next T lines constain one base number N (1 ≤ N ≤ 1000000).

Output

For each test case output a single line containing the number of different Dinostratus matrices corresponding to the base number. It is guaranteed that the answer is less than 2⁶³.

Example

Input:
7
1
10
100
1000
10000
100000
1000000
Output:
0
0
2
2382
257110
7475718
106889830

Note

You can try the problem DINONUM first.