P7325 [WC2021] Fibonacci

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$.

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.

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

**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: | Test Point ID | $n, m \le$ | Special Constraints | |:-:|:-:|:-:| | $1 \sim 2$ | $1000$ | None. | | $3 \sim 4$ | ${10}^5$ | $m$ is prime. | | $5 \sim 6$ | ${10}^5$ | $m = p_1 p_2 \cdots p_k$, where the $p_i$ are pairwise distinct primes. | | $7 \sim 10$ | ${10}^5$ | None. | Translated by ChatGPT 5