Practice on Toph

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

The Game Is Back On

By Sherlock221b · Limits 1s, 512 MB

Moriarty is bored again. When he gets bored, the only thing he wants to do is play with Sherlock. So he has given Sherlock another one of his puzzles. Will you help him solve it?

Moriarty has given Sherlock a number N. Now, Sherlock has to determine how many pairs of numbers (A, B) exists such that A and B are coprime with each other and LCM of A and B is N. Here, LCM means Least Common Multiple. Please note that two pairs (A, B) and (B, A) are considered the same and will be counted only once for the final answer.

Two numbers are coprime with each other if there is no number other than 1 that divides both of these numbers.

Input

In the first line of the input, there will be a number T (1 ≤ T ≤ 300) denoting the number of test cases. In the next T lines there will be a number N (1 ≤ N ≤ 1012) as described above.

Output

For each case, print the answer to Moriarty's puzzle in a single line.

Sample

InputOutput
2
3
42
1
4

Discussion

Statistics


50% Solution Ratio

tasmeemrezaEarliest, Dec '16

anparvez10Fastest, 0.2s

JisangainLightest, 131 kB

JisangainShortest, 494B

Submit

Login to submit

Editorial

Pre-requisite: Sieve of Eratosthenes Given two numbers A and B, we get the following - A ***** B = L...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.