Perhaps the first thing one notices when the Fibonacci sequence is reduced mod p is that it seems periodic.

For example :
F (mod 2) = 0 1 1 0 1 1 0 1 ...
F (mod 3) = 0 1 1 2 0 2 2 1 0 1 1 2 ...
F (mod 5) = 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 ...

We define Z(p) the number of zeros in fundamental period of Fibonacci numbers mod p (if it is periodic).
We just saw that Z(2) = 1, Z(3) = 2, and Z(5) = 4.

Input

The first line contains T, the number of test cases.
Each of the next T lines contains a prime number p.

Output

For each test case, print Z(p), or "Not periodic." without quotes if need.

Example

Input:
3
2
3
5
Output:
1
2
4

Constraints

You have four input files. The first two ones are those of Z124, the two others have higher constraints.

1 < T < 10^4
1 < p < 10^100, a prime number

Time limit is 2 times my unoptimized PY3.4 code time.
Good luck, and have fun ;-)