Excuse me for talking about problem from UVa, but I think, that some people were on this contest, so, please, help me with the algo. Here is the statement:

A pair of numbers has a unique LCM but a single number can be the LCM of more than one possible pairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, the number of different integer pairs with LCM is equal to N can be called the LCM cardinality of that number N. In this problem your job is to find out the LCM cardinality of a number.

Input

The input file contains at most 101 lines of inputs. Each line contains an integer N (0<N<=2*10^9). Input is terminated by a line containing a single zero. This line should not be processed.

Output

For each line of input except the last one produce one line of output. This line contains two integers N and C. Here N is the input number and C is its cardinality. These two numbers are separated by a single space.


Sample Input

2
12
24
101101291
0

Output for Sample Input

2 2
12 8
24 11
101101291 5

Factorize N. O(pi(sqrt(N))).
[ pi(x) - amount of primes until x. ]
N = p1^k1 * p2^k2 * ... * pT^kT...

lcm(u,v) = N, iff:

u or v (or both) has pi^ki, but not higher:

Lets write with what degree pi can be in u and v:
0 k1
1 k1
2 k1
...
k1-1 k1

k1 k1

k1 0
k1 1
k1 2
...
k1 k1-1

in total: k1*2+1 ways...
So total amount of pairs (u,v) such that lcm(u,v) == N is:
Q1 = (k1*2+1)*...*(kT*2+1).

But! We have counted pair (u,v) [u < v] two times! as an (u,v) and (v,u)....
Lets find amount of only distinct pairs (u != v)... Since there is only one pair (u,u) which lcm is N (u==N) we know that amount of pairs with distinct integers is: Q1-1.
So. Amount of ordered pairs is (Q1-1)/2...
And the answer is (Q1-1)/2 + 1...

Yes, it's simple, thank you, just my brains get hot and stupid in summer. Congratulations, you've got 5th place on the contest, it's rather cool!