Jimmy have to calculate a function f(x,y) where x and y are both integers in the range from 1 to n. When he knows f(x,y), he can easily derive f(k⋅x,k⋅y), where k is any integer from it by applying some simple calculations involving f(x,y) and k.
Note that the function f is not symmetric, so f(x,y) can not be derived from f(y,x).
For example if n=4, he only needs to know the answers for 11 out of the 16 possible input value combinations:
The other 5 can be derived from them:
f(2,2),f(3,3) и f(4,4) из f(1,1);
f(2,4) из f(1,2);
f(4,2) из f(2,1);
Consists of at most 600 lines. Each line contains an integer n (1≤n≤50000). The last line contains one zero and should not be processed.
For each input value of n print in a separate line the minimum number of function values Jimmy needs to know to compute all n2 values f(x,y).