Coprime Pairs

Time limit1sMemory limit128 MB

Summary

Given N, count the unordered pairs of coprime natural numbers whose least common multiple equals N.

Level: Medium5 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Let GCD(A, B) be the greatest common divisor of two natural numbers A and B, and let LCM(A, B) be their least common multiple. If A and B are coprime then GCD(A, B) = 1, and in that case LCM(A, B) = $A \times B$ .

Given a natural number N, several coprime pairs (A, B) can satisfy LCM(A, B) = N. For N = 30 there are four of them: (1, 30), (2, 15), (3, 10), (5, 6). Two pairs that differ only in order count as the same pair.

Count the coprime pairs of natural numbers whose least common multiple is N.

Input

The first line contains the number of test cases T. Each of the next T lines contains one natural number N, at most 100,000,000.

Output

For each test case, print on its own line the number of coprime pairs of natural numbers whose least common multiple is N, in input order.

Examples1

Example 1
Input
```
3
30
16
60060
```
Expected output
```
4
1
32
```