Z124H  Zeros of the fundamental Fibonacci period
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 ;)
hide comments
[Lakshman]:
20170218 16:08:51
Any specific test case for which I am getting wrong answer.


[Rampage] Blue.Mary:
20160724 09:54:22
This problem requires heavy constant optimization; the large input is (almost) generated uniformly at random.

Added by:  Francky 
Date:  20160723 
Time limit:  1.299s4.400s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Z124 