GCD - Extreme (II) [欧拉函数]

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1 < N < 4000001). The meaning of N is given in the PRoblem statement. Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.

Sample Input

10 100 200000 0

Sample Output

67 13015 143295493160

题解