Solve the programming task below in a Python markdown code block.
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