#include "bits/stdc++.h"

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define ar array

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int, int>;

const ll INF = 7e18;

template<typename T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}


using ll = long long;

const int MOD = 1e9 + 7;

struct mint {
    int value;

    mint(ll x = 0) {
        if (x >= MOD || x < 0) {
            x %= MOD;
            if (x < 0) x += MOD;
        }
        value = x;
    }

    mint &operator+=(const mint &b) {
        value += b.value;
        if (value >= MOD) value -= MOD;
        return *this;
    }

    mint &operator-=(const mint &b) {
        value -= b.value;
        if (value < 0) value += MOD;
        return *this;
    }

    mint &operator*=(const mint &b) {
        value = (1ll * value * b.value) % MOD;
        return *this;
    }

    mint inv();
};

mint operator*(mint a, const mint &b) {
    return a *= b;
}

mint operator+(mint a, const mint &b) {
    return a += b;
}

mint operator-(mint a, const mint &b) {
    return a -= b;
}

mint power(mint a, ll b) {
    mint r = 1;
    for (; b; b >>= 1, a *= a) if (b & 1) r *= a;
    return r;
}

mint mint::inv() {
    return power(*this, MOD - 2);
}


void solve() {
    constexpr int N = 1e7, M = 2e7;
    vector<int> minp(N + 1);
    vector<mint> fact(M + 1), rfct(M + 1);

    fact[0] = 1;
    for (int i = 1; i <= M; ++i) fact[i] = i * fact[i - 1];
    rfct[M] = fact[M].inv();
    for (int i = M; i >= 1; --i) rfct[i - 1] = rfct[i] * i;

    for (int i = 2; i <= N; ++i) {
        if (minp[i]) continue;
        minp[i] = i;
        if ((long long) i * i > N) continue;
        for (int j = i * i; j <= N; j += i) {
            if (!minp[j]) minp[j] = i;
        }
    }

    auto c = [&](int n, int k) {
        if (0 <= k && k <= n)
            return fact[n] * rfct[k] * rfct[n - k];
        else return mint(0);
    };

    auto T = [&](int n, int k) {
        return c(n - 1, k - 1);
    };

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        mint ans = 0;
        int big = (n - 1) / 2;
        {
            {
                // identity
                ans += T(n, m);
                ans -= m * T(n - big, m);
            }

            vector<pair<int, int>> prs;
            for (int x = m; x != 1;) {
                int p = minp[x];
                int cp = 0;
                while (x % p == 0) {
                    cp++;
                    x /= p;
                }
                prs.emplace_back(p, cp);
            }

            vector<int> divs;
            function<void(int, int)> rec = [&](int i, int d) {
                if (i == divs.size()) {
                    divs.push_back(d);
                    return;
                }
                rec(i + 1, d);
                for (int j = 1; j <= prs[i].second; ++j) {
                    d *= prs[i].first;
                    rec(i + 1, d);
                }
            };
            rec(0, 1);
            sort(all(divs));
            vector<int> cnt(divs.size());
            for (int i = (int) divs.size() - 1; i >= 0; --i) {
                int g = divs[i];
                cnt[i] = m / g;
                for(int j = i + 1; j < divs.size(); ++j) {
                    if (divs[j] % g == 0) {
                        cnt[i] -= cnt[j];
                    }
                }
            }
            cnt.back()--;


            rep(i, divs.size()) {
                int g = divs[i];
                if (g == m) continue;
//                cerr << g << ' ' << cnt[i] << '\n';
                int parts = m / g;
                assert(parts >= 2);
                if (n % parts != 0) {
                    continue;
                }
                int m1 = g;
                int n1 = n / parts;
                ans += T(n1, m1) * mint(cnt[i]);
            }
//            cerr << "END\n";
        }
        {
            // reverse
            // f(i) = (n - 1 - i + s) % n
            auto solve = [&](int s) {
                if (m % 2 == 1) {
                    // unique solution
                    int pairs = (m - 1) / 2;
                    int ones = 1;
                    mint value = T((n + 1) / 2, pairs + ones);
                    value -= T((n - big + 1) / 2, pairs + ones);
                    return value;
                } else if ((s - 1) % 2 != 0) {
                    // no solution
                    int pairs = m / 2;
                    if (n % 2 != 0) return mint(0);
                    return T(n / 2, pairs);
                } else {
                    // two solutions
                    int pairs = (m - 2) / 2;
                    int ones = 2;
                    mint value = 0;
                    rep(mask, 4) {
                        int q = __builtin_popcount(mask);
                        if ((q + n) % 2 == 0) {
                            value += T((n + q) / 2, pairs + ones);
                            if (big % 2 == 0) {
                                value -= T((n + q - big) / 2, pairs + ones) * 2;
                            } else {
                                rep(t, 2) {
                                    if (mask & (1 << t)) {
                                        value -= T((n + q - (big + 1)) / 2, pairs + ones);
                                    } else {
                                        value -= T((n + q - (big - 1)) / 2, pairs + ones);
                                    }
                                }
                            }
                        }
                    }
                    return value;
                }
            };
            if (m % 2 == 1) {
                ans += solve(0) * m;
            } else {
                ans += (solve(1) + solve(0)) * (m / 2);
            }
        }
        ans *= mint(m * 2).inv();
        cout << ans.value << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}