DINOMAT - Dinostratus Matrices

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

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

For example the matrices

 2   6   18 
 4   12   36 
   
18  198 
 21   126   4158 
 147   882   29106 
   
10  100  4000 
 50   1000   20000 
 10000   100000   1000000 

are Dinostratus. And the following matrices are not:


 2   6   18 
 4   12   54 
   
 2   4   8 
 4   8   16 
   
36  12 
 18   6   2 
 9   3   1 

 

Let's define the element a3,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 ai,jbi,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 263.

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.


Added by:feodorv
Date:2020-04-14
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.