Problem Description
You are given a positive integer m. Calculate the product of all positive integers less then or equal to m and coprime with m, and give the answer modulo m.
Input
There are multiple tests end with EOF, each test contains only a positive integer m ≤ 10^9 in a line. The number of tests is no more than 5000.
Output
In the output file you should write the answer to the task.
Sample Input
1
2
3
4
5
6
7
Sample Output
0
1
2
3
4
5
6