Ryan is completing his math assignment where he stumbles upon a curious problem: find the number of pairs of positive integers ~(a,b)~ that satisfy the equation ~\frac{1}{a} + \frac{1}{b} = \frac{1}{2}~. The assignment is too easy for him, so he generalises the problem: find the number of ordered pairs of positive integers ~(a,b)~ which satisfy ~\frac{1}{a} + \frac{1}{b} = \frac{1}{c}~ for a given positive integer ~c~.

Can you help Ryan solve this redesigned math problem?

Constraints

For all subtasks:

~1 \leq T \leq 10^5~

~1 \leq c \leq 10^7~

Subtask 1 [5%]

~c = 2~

Subtask 2 [45%]

~1 \leq T \leq 10^3~

~1 \leq c \leq 5 \times 10^4~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains a single integer ~T~, the number of test cases.

The following ~T~ lines each contain a single integer ~c~.

Output Specification

For each test case, print a single integer, the number of ordered positive integer pairs ~(a,b)~ that satisfy ~\frac{1}{a}+\frac{1}{b}=\frac{1}{c}~. It can be proven that the answer can fit in a 64-bit signed integer.

Sample Input

2
1
3

Sample Output

1
3

Sample Explanation

For the first test case, only ~(2,2)~ satisfies the condition.

For the second test case, ~(4,12)~, ~(6,6)~ and ~(12,4)~ satisfy the condition.