Coprime Pairs

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.

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.

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.