He thinks ZHC can never solve the math problem even given three years. WCM laughs and laughs within himself. But surprising to him, ZHC spent only 20 minutes to solve it perfectly. Now WCM wants to know whether the problem is a simple problem. Can you solve it in 20 minutes? The problem is described below.

Given a positive integer N, you are to find the number of solutions of the module equation (x * x = 1) mod N and 0 ≤ x < N. The mod operator is defined as: A mod B = C if and only if there exists an integer k satisfying that A = k * B + C and 0 ≤ C < B. For example, 10 mod 3 = 1, 20 mod 5 = 0, 3 is a solution of (x * x = 1) mod 8 and 5 is a solution of (x * x = 1) mod 6.

Input

A case with N = 0 denotes the end of input, which should not be proceeded.

Output

For each test case, output a line containing the single integer answer.

Sample Input

1
2
3
4
1673175496
0

Sample Output

0
1
2
2
16