Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

By maruf089 · Limits 1s, 256 MB

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

InputOutput
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)$.

Statistics

85% Solution Ratio

YouKnowWhoEarliest, 1M ago

likhon5Fastest, 0.0s

YouKnowWhoLightest, 131 kB

Deshi_TouristShortest, 359B