Description

As everyone knows, student Xiaocong is good at calculations, especially at computing binomial coefficients. But after studying binomial coefficients thoroughly, Xiaocong lost interest in them and started researching sequences.

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

Now you are 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, m$, representing the number of queries and the modulus used in each computation.

The next $n$ lines each contain two integers $a, b$, representing the values of $F_0$ and $F_1$ in one query.

Output Format

For each query, output one integer $p$ on a single line as the answer. If such a $p$ does not exist, output -1.

4 5
0 1
1 2
2 3
3 4

0
3
2
-1

1 6
4 4

3

见附件中的 fib/fib3.in

见附件中的 fib/fib3.ans

见附件中的 fib/fib4.in

见附件中的 fib/fib4.ans

Hint

Constraints

For all testdata: $1 \le n, m \le {10}^5$, $0 \le a, b < m$.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5