特判掉 \(a=0\) 或 \(b=0\) 的情况，本质上就是求解最小的 \(p\) 满足 \(af_{p-1}+bf_p\equiv 0 \pmod{m}\)。

置 \(b\) 为 \(-b\)，变为求解 \(af_{p-1}\equiv bf_p \pmod m\)，若 \(m\) 为质数，那么可以直接变换为 \(ab^{-1}\equiv f_pf_{p-1}^{-1}\pmod m\)，预处理一下所有的 \(f_pf_{p-1}^{-1} \pmod m\) 后对每次询问查表即可。

这对我们的思路有一定的启发，当 \(m\) 不是质数的时候可不可以将 \(a,b\) 相关的移到等式左边而等式右边只留下和 \(a,b\) 无关的，预处理后查表呢？

为了将 \(b\) 移到等式左边，我们需要先保证 \(\gcd(b,m)=1\)，这样 \(b\) 才有逆元。设 \(d=\gcd(a,b,m)\)，那么 \(\frac{a}{d}f_{p-1}\equiv \frac{b}{d}f_p \pmod{\frac{m}{d}}\) ，然后设 \(d'=\gcd(\frac{b}{d},\frac{m}{d})\)，可以得到 \(\frac{a}{d}\frac{f_{p-1}}{d'}\equiv \frac{b}{dd'}f_p \pmod{\frac{m}{d}}\)，再移项变为 \(\frac{a}{d}\left(\frac{b}{dd'}\right)^{-1}\frac{f_{p-1}}{d'}\equiv f_p\pmod{\frac{m}{d}}\)。

现在我们想要把 \(\frac{f_{p-1}}{d'}\) 移到右边去，这需要保证 \(\gcd(\frac{f_{p-1}}{d'},\frac{m}{d})=1\)，恰好这是一定满足的：设 \(\gcd(\frac{f_{p-1}}{d'},\frac{m}{d})=x \ne 1\)，那么也就是说 \(x \mid f_p\) 并且 \(x \mid f_{p-1}\)，这和斐波那契数列相邻两项互质矛盾！

于是我们可以放心地移项变为 \(\frac{a}{d}\left(\frac{b}{dd'}\right)^{-1}\equiv f_p\left(\frac{f_{p-1}}{d'}\right)^{-1}\pmod{\frac{m}{d}}\)

预处理时枚举 \(d\) 和 \(d'\) 即可，时间复杂度为 \(m\) 的约数的约数个数和，再在std::map中查表太慢了。

注意到最后一步移项中我们保证了 \(\gcd\left(\frac{f_{p-1}}{d'},\frac{m}{d}\right)=1\)，这要求 \(d'=\gcd\left(f_{p-1},\frac{m}{d}\right)\)，是唯一确定的，不需要枚举。

因此预处理时只需要枚举 \(d\) 即可，有 \(m\) 的约数个数个，可以通过，代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, m;
inline int Plus(int a, int b, const int mod = m) {return a + b >= mod ? a + b - mod : a + b; }
inline int Minus(int a, int b, const int mod = m) {return a - b < 0 ? a - b + mod : a - b; }
void exgcd(int a, int b, int &d, int &x, int &y) {
    if(!b) {d = a, x = 1, y = 0; return; }
    exgcd(b, a % b, d, y, x);
    y -= (a / b) * x;
}
inline int inv(int a, const int mod) {
    int d, x, y;
    exgcd(a, mod, d, x, y);
    assert(d == 1);
    return (x % mod + mod) % mod;
}

map<tuple<int, int, int>, int> Map;
int f[N * 6];
inline void init() {
    f[1] = 1;
    for(int d = 1; d < m; d ++) {
        if(m % d) continue;
        const int mod = m / d;
        for(int p = 2; ; p ++) {
            f[p] = Plus(f[p - 1], f[p - 2], mod);
            if(f[p - 1] == 0 && f[p] == 1) break;
            if(f[p - 1] == 0 || f[p] == 0) continue;
            int d1 = __gcd(f[p - 1], mod);
            int val = 1ll * f[p] * inv(f[p - 1] / d1, mod / d1) % (mod / d1);
            if(!Map.count({d, d1, val}))
                Map[{d, d1, val}] = p;
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    init();

    while(n --) {
        int a, b; cin >> a >> b;
        if(a && b) {
            b = Minus(0, b);
            int d = __gcd(m, __gcd(a, b));
            int d1 = __gcd(b / d, m / d);
            int val = 1ll * a / d * inv(b / d / d1, m / d / d1) % (m / d / d1);
            if(Map.count({d, d1, val})) cout << Map[{d, d1, val}] << '\n';
            else cout << "-1" << '\n';
        } else cout << (a == 0 ? "0" : "1") << '\n';
    }

    return 0;
}