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.
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.
In the output file you should write the answer to the task.