SP27519 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.

The first line contains _T_, the number of test cases. Each of the next _T_ lines contains a prime number _p_.

For each test case, print _Z_(_p_), or "Not periodic." without quotes if need.