Problem Description

As is well-known, Xiao Cong excels in computation, especially in calculating combinatorial numbers. However, after extensive research on combinatorial numbers, Xiao Cong has lost interest in them and has turned to studying sequences.

We define \( F_0 = a \), \( F_1 = b \), and \( F_i = (F_{i-1} + F_{i-2}) \bmod m \) for \( i \ge 2 \).

Given \( n \) queries, for each query, find the smallest integer \( p \) such that \( F_p = 0 \).

Input Format

The first line contains two integers \( n \) and \( m \), representing the number of queries and the modulus for each query, respectively.

The next \( n \) lines each contain two integers \( a \) and \( b \), representing the values of \( F_0 \) and \( F_1 \) for a query.

Output Format

For each query, output a single line containing an integer \( p \) which is the answer. If such a \( p \) does not exist, output -1.

Sample Input and Output

Sample Input #1

4 5
0 1
1 2
2 3
3 4

Sample Output #1

0
3
2
-1

Sample Input #2

1 6
4 4

Sample Output #2

3

Sample Input #3

See attached file fib/fib3.in

Sample Output #3

See attached file fib/fib3.ans

Sample Input #4

See attached file fib/fib4.in

Sample Output #4

See attached file fib/fib4.ans

Notes

[Data Range]

For all test cases: \( 1 \le n, m \le 10^5 \), \( 0 \le a, b < m \).

Specific constraints for each test point are as follows:

见题面 Input 部分

见题面 Output 部分