Love you Ten thousand years

Time Limit: 3000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2619
64-bit integer IO format: %I64d      Java class name: Main

Description

Love you Ten thousand years------Earth's rotation is a day that is the representative of a day I love you. True love, there is no limit and no defects. Earth's revolution once a year, it is on behalf of my love you more than a year. Permanent horizon, and my heart will never change ……

We say that integer x, 0 < x < n,(n is a odd prime number) is a LovePoint-based-on n if and only if the set { (xi mod n) | 1 <= i <= n-1 } is equal to { 1, ..., n-1 }. For example, the powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a LovePoint-based-on 7.
Now give you a integer n >= 3(n will not exceed 231).
We say the number of LovePoint-based-on n is the number of days the earth rotating.
Your task is to calculate the number of days someone loved you.

Input

Each line of the input contains an integer n. Input is terminated by the end-of-file.

Output

For each n, print a single number that gives the number of days someone loved you.

Sample Input

5

Sample Output

2

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .