【题目描述】

不从历史中吸取教训的人注定要重蹈覆辙。输入模数 $p$，求 $Fibonacci$ 数模 $p$ 的循环节。详细的题意如下：

定义数列 ${Fn}$，其中 $F0 = 0, F1 = 1, Fi = Fi−1 + Fi−2(i ≥ 2)$。

输入 p，求出最小的正整数 n，使得 $Fn mod p = F0$, $Fn+1 mod p = F1$。

【输入格式】

第一行，一行一个整数 t 表示数据组数。

接下来 t 行，每行一个整数 p。

【输出格式】

输出共 t 行，对于每个输入的 p，输出一行一个整数，表示循环节。

【样例输入】

10
2
3
4
5
6
7
8
9
10
11

【样例输出】

3
8
6
20
24
16
12
24
60
10

【数据规模与约定】

对于 100% 的数据，满足 $t = 10, 2 ≤ p ≤ 10^9$。

对于 30% 的数据，满足 $p ≤ 10^6$。

对于 30% 的数据，满足 p 是质数。

对于 20% 的数据，满⾜ p 是质数的次幂（次幂或以上）。以上三部分数据不相交。