Fibonacci

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

We consider the Fibonacci sequence f where f(0) = 0, f(1) = 1 and f(n) = f(n - 1) + f(n - 2) for n ≥ 2. For given x(0), one can define another sequence x that x(n) = f(x(n-1)). Now you need to find the minimum n such that x(n) ≡ x(0) (mod p).

Input

The first line contains an integer T indicating the number of test cases. Then for each test case, a line consists of two integers x(0) and p where 0 ≤ x(0) ≤ $10^9$ and 1 ≤ p ≤ 200000.

Output

For each test, output the minimum n in a line, or -1 if it is impossible.

Sample Input

5 6 4 8 11 9 11 12 11 13 11

Sample Output

3 3 -1 1 1
Hint
In the first case, x(0) = 6 ≡ 2 (mod 4), x(1) = f(6) = 8 ≡ 0 (mod 4) and x(2) = f(8) = 21 ≡ 1 (mod 4), and therefore x(3) = f(21) = 10946 ≡ 2 (mod 4).

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)

提交代码