小白学Fibonacci之二

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

已知fibonacci数列f[1]=f[1]=1,f[n]=f[n-1]+f[n-2].                                                                                              
给定p,求最小的正整数m,使得对于所有的n,f[n]=f[n+m] (mod p). 

Input

包含多组数据<=20.
每组数据一行,一个数字p(1<=p<=2*10^9),p的最大因子不超过10^6.
 

Output

 每组数据输出一行,一个数字m.
 

Sample Input

5 
11 
19 
61 
17 
67890

Sample Output

10
18
60
36
4440

Hint

 

Source