Count Quadruplets

LCM is an abbreviation used for Least Common Multiple in Mathematics. The LCM of two positive integers is the smallest positive integer that is divisible by both the integers.

We can say that $LCM (a, b, c, d) = L$, if and only if $L$ is the smallest integer which is divisible by $a$, $b$, $c$ and $d$.

You will be given $L$. You have to count number of Quadruplets $(a, b, c, d)$ such that $LCM (a, b, c, d) = L$.

Input

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

Each test case consists of a single integer $L (1\leq L \leq 10^9)$, the LCM of the Quadruplets.

Output

For each test case, print the number of such quadruplets.

Sample

Input	Output
2 2 3	15 15

For $L = 2$, then we have $15$ Quadruplets $-$

$(1\ 1\ 1\ 2)$, $(1\ 1\ 2\ 1)$, $(1\ 1\ 2\ 2)$, $(1\ 2\ 1\ 1)$, $(1\ 2\ 1\ 2)$, $(1\ 2\ 2\ 1)$, $(1\ 2\ 2\ 2)$, $(2\ 1\ 1\ 1)$, $(2\ 1\ 1\ 2)$, $(2\ 1\ 2\ 1)$, $(2\ 1\ 2\ 2)$, $(2\ 2\ 1\ 1)$, $(2\ 2\ 1\ 2)$, $(2\ 2\ 2\ 1)$, $(2\ 2\ 2\ 2)$.