Three Cats and Two Omens

Time limit: 3000 msMemory limit: 64 MB

At the moonlit fish market, Griffithm presents Gats and two other cats with a positive integer $N$ . Each cat chooses one positive integer, producing an ordered triple $(A,B,C)$ . The cats are distinct, so changing which cat receives a value produces a different triple.

The chest of fish opens if

$A \times B \times C=N$

and at least one of the following omens occurs:

$\gcd(A,B,C)$ is a perfect square;
$\operatorname{lcm}(A,B,C)$ is a perfect cube.

A triple satisfying both omens is counted only once. A perfect square has the form $k^2$ , and a perfect cube has the form $k^3$ , for some positive integer $k$ . In particular, $1$ is both a perfect square and a perfect cube.

For each given value of $N$ , count the feast-worthy ordered triples $(A,B,C)$ .

Input

The first line contains an integer $T$ ( $1 \le T \le 500$ ), the number of test cases.

Each of the next $T$ lines contains one integer $N$ ( $1 \leq N \leq 10^{12}$ ).

Output

For each test case, print one integer: the number of feast-worthy ordered triples.

Samples

Sample 1

Input

Output

For $N=1$ , the only triple is $(1,1,1)$ . For $N=2$ , the valid triples are the three permutations of $(2,$ . For , there are ten ordered product triples, and only satisfies neither omen. For , exactly ordered triples are feast-worthy.

Three Cats and Two Omens

Input

Output

Samples

Sample 1

Submit

Submissions