## 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