GCD#1146
Sign in

GCD

1 second
128 megabytes
Very easy

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

prb1146.gif

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

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

prb1146_1.gif

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

Input

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

Output

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

Examples

Example 1

Loading
Loading