PISANO  Modular Fibonacci Period
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 20170211, after compiler changes ; new TL. My old Python code end in 1.92s.
hide comments
Erick Leonardo de Sousa Monteiro [UEA]:
20191114 13:55:36
Had to use __int128_t to pass. Good problem. 

sanyam19:
20180610 11:06:32
i am getting tle. ID 21811838


waddlepoof:
20140728 21:56:33
haha, I had an overflow error... 

waddlepoof:
20140625 19:44:25
I do not know if I totally missed the point or if current version of GHC being 32bit is a great impact on performance, because on my incredibly slow computer I've managed to decrease running time from 49 seconds to 5 seconds for 10000 randomly generated [1..10^12] integers.


[Lakshman]:
20140501 11:46:47
@Francky I think I have correct solution but getting WA can you help me? if I am doing something wrong.


Federico LebrÃ³n:
20130627 20:56:31
This was a lot of fun, thanks!


Damian Straszak:
20130220 23:04:18
Nice problem. Unfortunately I wasn't able to get AC in Python. This is because my solutions still needs some bruteforce to work.


Ninja coder:
20130128 09:47:58
@Tjandra: My code seems to be smaller than your comment.


Ehor Nechiporenko:
20130124 12:08:50
Francky, thanks a lot for this problem! It was a great enjoy for me to solve it!


Ehor Nechiporenko:
20130123 22:40:55
Hey Francky, do you have a tricky tests with big prime numbers, like a 999999999989? 
Added by:  Francky 
Date:  20130120 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 