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

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.

For each test case, on a single line, print K(M), or "Not periodic." without quotes if need.