Z124H - Zeros of the fundamental Fibonacci period

no tags 

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]: 2017-02-18 16:08:51

Any specific test case for which I am getting wrong answer.

=(Francky)=> I saw WA for 2 out of 3 test cases given in description. Using brute force, you'll find some others. Good luck for debug ; you're not so far.

Last edit: 2017-02-19 17:46:25
[Rampage] Blue.Mary: 2016-07-24 09:54:22

This problem requires heavy constant optimization; the large input is (almost) generated uniformly at random.

By my experiment, Python 2.7/3.4 and C++ can easily pass the TL with the desired method; other languages like PIKE, RUBY are very hard to to do that.

=(Francky)=> Many thanks for your feedback, and congrats for your AC.

Last edit: 2016-07-24 11:03:57

Added by:Francky
Date:2016-07-23
Time limit:1.299s-4.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Z124