Read problems statements in Mandarin Chinese here

------ Problem Statement ------

As we know, Fibonacci Number is defined as

F_{n}=n if n ≤ 1
F_{n}=F_{n-1}+F_{n-2}, otherwise

Now this problem is quite simple: you are given one prime number P and one non-negative integer C

You are expected to find the smallest non-negative integer n, such that

F_{n}≡C(mod P)
The definition of "mod" could be found here:

here

------ Input ------

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

Only one line of each test case, which contains two integers C and P denoting the number described above.

------ Output ------

For each test case, output a single line containing one integer indicates the smallest n. If such n do not exist, output -1 instead

------ Constraints ------

1 ≤ T ≤ 100

11 ≤ P ≤ 2000000000 and is one prime number

0 ≤ C ≤ P-1

(P Mod 10) is square number

------ Example ------

Input:
4
0 11
16 19
18 19
4 19

Output:
0
14
16
-1

Hint:
Here are the first few fibonacci number when mod by 19:

n
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
F_{n}(mod 19)
0 1 1 2 3 5 8 13 2 15 17 13 11 5 16 2 18 1 0 1

见题面

见题面