Time Limit:2000ms Memory Limit:65536KB

Description

You may be very familiar with the divisor funciton d(n) and the divisor sum
function sigma(n), which denote the number of positive divisors of n and the sum
of all positive divisors of n respectively. One day, when Sherry was studying
number theory and found these functions were so dull so she defined new a
function p(n) by the product of all positive divisors of n. She asked Edogawa
Conan to do some calculation on this function. Since p(n) can be extremely large
for some specific numbers, so she only wonder the number of positive divisors of
p(n) for some given positive integer n. But poor Conan always has so many cases
to solve, So He asked you for help.

Input

The first line contains an integer T which stands for the number of test cases.
each case is a line with a single integer n, 1
<= n <= 1000000.

Output

Output one line the each test case, with a single integer d(p(n)), which means
the number of positive divisors of the product of all positive divisors of n.
We guarantee the answer can be represented by long long.


Sample Input

3
4
6
9

Sample Output

4
9
4

Hint

p(4) = 1 * 2 * 4 = 8, the positive divisors of 8 are 1, 2, 4, 8, d(8) = 4, so the
result is 4 for the first sample case.

Author

Cauchy

Source

Preliminary (Single)