As is well known, Xiao Cong is good at calculation, especially at calculating combinations. However, having studied combinations thoroughly, Xiao Cong has lost interest in them and has started studying sequences.
We define $F_0 = a$, $F_1 = b$, and $F_i = (F_{i-1} + F_{i-2}) \pmod m$ for $i \ge 2$.
Given $n$ queries, for each query, find the smallest integer $p$ such that $F_p = 0$.
Input
The first line contains two integers $n$ and $m$, representing the number of queries and the modulus for each calculation, 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
For each query, output a single integer $p$ representing the answer. If no such $p$ exists, output -1.
Constraints
For all test cases: $1 \le n, m \le 10^5$, $0 \le a, b < m$.
| Test Case ID | $n, m \le$ | Special Constraints |
|---|---|---|
| $1 \sim 2$ | $1000$ | None |
| $3 \sim 4$ | $10^5$ | $m$ is a prime number |
| $5 \sim 6$ | $10^5$ | $m = p_1 p_2 \cdots p_k$, where $p_i$ are distinct primes |
| $7 \sim 10$ | $10^5$ | None |
Examples
Input 1
4 5 0 1 1 2 2 3 3 4
Output 1
0 3 2 -1
Input 2
1 6 4 4
Output 2
3
Examples 3
See fib/fib3.in and fib/fib3.ans in the contestant directory.
Examples 4
See fib/fib4.in and fib/fib4.ans in the contestant directory.