时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
We consider the Fibonacci sequence 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).
输入描述:
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) ≤ 109 and 1 ≤ p ≤ 200000.
输出描述:
For each test, output the minimum n in a line, or −1 if it is impossible.
示例1
输入
复制
5
6 4
8 11
9 11
12 11
13 11
说明
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).