Given the value of n, you have to find the value of G, where

Here GCD(i, j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

Here GCD() is a function that finds the greatest common divisor of the two input numbers.

Input

Contains at most 100 lines of inputs. Each line contains an integer n (1 < n < 501). The last line contains n = 0 and is not processed.

Output

For each input integer n print in a separate line the corresponding value of G.