Practice on Toph

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

Count Quadruplets

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)=LLCM (a, b, c, d) = L, if and only if LL is the smallest integer which is divisible by aa, bb, cc and dd.

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

Input

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

Each test case consists of a single integer L(1L109)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=2L = 2, then we have 1515 Quadruplets -

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

    Discussion

    Statistics


    85% Solution Ratio

    YouKnowWhoEarliest, 1M ago

    likhon5Fastest, 0.0s

    YouKnowWhoLightest, 131 kB

    Deshi_TouristShortest, 359B

    Submit

    Login to submit

    Editorial

    Prerequisite: Prime Factorization(Number Theory)/ Dynamic Programming Explanation: First let us unde...