#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1'000'000'007;
constexpr int N = 10'000'228;
constexpr int M = 2*N;

int minp[N+1], fact[M+1], rfct[M+1], phi[N+1];
int rev(int a, int m = MOD) {
    return a == 1 ? 1 : m - (ll)m*rev(m%a,a)/a;
}
int c(int n, int k) {
    return 0 <= k && k <= n ? (ll)fact[n]*rfct[k]%MOD*rfct[n-k]%MOD : 0;
}

void mod_add(int& a, int b) {
    a += b;
    if (a >= MOD) a -= b;
}

void mod_sub(int& a, int b) {
    a -= b;
    if (a < 0) a += MOD;
}

int cnt(int n, int mp, int sn) {
    if (n < 0) return 0;
    if (sn) {
        int a = cnt(n, mp+1, sn-1);
        mod_add(a, cnt(n+1, mp+1, sn-1));
        return a;
    } else {
        const int a = n%2 ? 0 : c(n/2-1, mp-1);
        return a;
    }
}

int solve(int n, int m) {
    vector<int> divs{{1}};
    for (int j = m; j != 1; ) {
        const int p = minp[j], s = divs.size();
        // cout << j << ", p=" << p << endl;
        int k = 0;
        while (j % p == 0) j /= p, ++k;
        for (int i = 0; i < s*k; ++i)
            divs.push_back(divs[i]*p);
    }

    int ans = 0;
    for (int d : divs) {
        if (d == m) {
            mod_add(ans, c(n-1, m-1));
            ans = (ans + (ll)(MOD - m)*c(n/2, m-1))%MOD;
            // cout << "d=" << d << ": " << ans << " " << 1 << endl;
        } else {
            const int cnt = m / d;
            if (n % cnt == 0)
                ans = (ans + (ll)c(n/cnt-1, d-1)*phi[cnt])%MOD;
            // cout << "d=" << d << ": " << ans << " " << phi[cnt] << endl;
        }
    }
    // cerr << ans << " half" << endl;

    if (m % 2) {
        ans = (ans + (ll)m*cnt(n, m/2, 1))%MOD;
        ans = (ans + (ll)(MOD-m)*cnt(n/2+1, m/2, 1))%MOD;
    } else {
        ans = (ans + (ll)(m/2)*cnt(n, m/2, 0))%MOD;
        ans = (ans + (ll)(m/2)*cnt(n, m/2-1, 2))%MOD;
        ans = (ans + (ll)(MOD-m)*cnt(n/2+1, m/2-1, 2))%MOD;
    }
    // cerr << ans << "!" << endl;

    ans = (ll)ans*rev(2*m)%MOD;
    return ans;
}

int solve_brute(int n, int m, int max, vector<int>& st) {
    if (n < m) return 0;
    if (!m) {
        if (n != 0) return 0;
        auto v = st;
        for (int t = 2; t--; ) {
            reverse(v.begin(), v.end());
            for (int i = 0; i < st.size(); ++i) {
                rotate(v.begin(), v.begin()+1, v.end());
                if (v < st) return 0;
            }
        }
        // for (int x : st) cout << x << ' ';
        // cout << endl;
        return 1;
    }
    int ans = 0;
    st.push_back(0);
    for (int x = 1; x <= n && x <= max; ++x) {
        st.back() = x;
        ans += solve_brute(n-x, m-1, max, st);
    }
    st.pop_back();
    return ans;
}

int solve_brute(int n, int m) {
    vector<int> st;
    int ans = solve_brute(n, m, (n-1)/2, st);
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    for (int i = 2; i <= N; ++i) {
        if (minp[i]) continue;
        minp[i] = i;
        if ((ll)i*i > N) continue;
        for (int j = i*i; j <= N; j += i)
            if (!minp[j]) minp[j] = i;
    }

    phi[1] = 1;
    for (int i = 2; i <= N; ++i) {
        const int p = minp[i];
        const int j = i / p;
        if (p == minp[j]) phi[i] = phi[j] * p;
        else              phi[i] = phi[j] * (p-1);
    }

    fact[0] = 1;
    for (int i = 1; i <= M; ++i) fact[i] = (ll)fact[i-1]*i%MOD;
    rfct[M] = rev(fact[M]);
    for (int i = M; i >= 1; --i) rfct[i-1] = (ll)rfct[i]*i%MOD;

    // for (int m = 3; m <= 4; ++m) {
    //     cerr << "m=" << m << endl;
    //     for (int n = m; n <= 100; ++n) {
    //         int pans = solve(n, m);
    //         int jans = solve_brute(n, m);
    //         if (pans != jans) {
    //             cout << "WA!" << endl;
    //             cout << n << " " << m << endl;
    //             cout << "pans=" << pans << endl;
    //             cout << "jans=" << jans << endl;
    //             exit(0);
    //         }
    //     }
    // }

    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        int ans = solve(n, m);
        cout << ans << '\n';
    }
}