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

For example :
F (mod 4) = 0 1 1 2 3 1 0 1 1 2 3 ...
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 K(M) the period of the Fibonacci sequence reduced mod M if it is periodic.
We just saw that K(4) = 6 and K(5) = 20.

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are one integer M.

Output

For each test case, on a single line, print K(M), or "Not periodic." without quotes if need.

Example

Input:
3
4
5
6
Output:
6
20
24

Constraints

1 < T < 10^4
1 < M < 10^12

Edit 2017-02-11, after compiler changes ; new TL. My old Python code end in 1.92s.