UOJ Logo

NOI.AC

1S 512MB

#130. B君的第一题

统计

【题目描述】

不从历史中吸取教训的人注定要重蹈覆辙。输入模数 $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 是质数的次幂(次幂或以上)。以上三部分数据不相交。