#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int N=10000010;
int fac[N],ifac[N];
bool ntp[N];
int p[N>>2],pn,phi[N];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1LL*ans*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return ans;
}
int C(int a,int b) {
    if(a < b) return 0;
    if(b < 0) return 0;
    return 1LL * fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=1LL*fac[i-1]*i%mod;
    }
    ifac[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=0;--i){
        ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
    }
    ntp[1]=1;
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!ntp[i])p[++pn]=i,phi[i]=i-1;
        for(int j=1;j<=pn&&i*p[j]<=n;++j){
            ntp[p[j]*i]=1;
            if(i%p[j]==0){
                phi[p[j]*i]=phi[i]*p[j];
                break;
            }
            else{
                phi[p[j]*i]=phi[i]*(p[j]-1);
            }
        }
    }
}
int S(int l,int r,int m) { /// sum C(i,m)
    if(l > r) return 0;
    if(l == 0) return C(r + 1 , m + 1) ;
    int ans = C(r + 1 , m + 1) ;
    ans = (ans - C(l , m + 1) + mod) % mod;
    return ans;
}
int S2(int l,int r,int m) { /// sum i*C(i,m)
    if(l > r) return 0;
    int ans = 1LL * (m+1) * C(r+2 , m+2) % mod;
    if(l == 0) return (ans - S(l , r , m) + mod) % mod;
    ans = (ans - 1LL * (m + 1) * C(l + 1 , m + 2) % mod + mod) % mod;
    ans = (ans - S(l , r , m) + mod) % mod;
    // int ans = 0;
    // for(int i = l ; i <= r;i++) ans = (ans + 1LL * i * C(i , m )) % mod;
    return ans;
}
typedef pair<int,int> pii;
pii work(int l,int r,int n) {
    if((n - l) % 2 != 0) l++ ;
    if((n - r) % 2 != 0) r-- ;
    if(l > r) return {1, 0} ;
    l = (n-l)/2 - 1;
    r = (n-r)/2 - 1;
    r = max(r , 0) ;
    if(r > l) return {1 , 0} ;
    return {r , l} ;
}
void Solve(){
    int n , m ; cin >> n >> m;
    vector<int> vd;
    for(int i = 1 ; i * i <= m;i++) {
        if(m % i == 0) {
            vd.push_back(i) ;
            if(i * i != m) vd.push_back(m / i) ;
        }
    }
    int ans = 0;
    for(auto d : vd) {
        if(n % (m / d) != 0) continue ;
        if(d == m) continue ;
       ans = (ans + 1LL * phi[m / d] * C(n / (m / d) - 1 , d - 1)) % mod;
    }
    int lm = (n + 1) / 2;

    ans = ((ll)ans + C(n-1,m-1) - 1LL * m * S(0 , n - lm - 1 , m - 2) % mod + mod) % mod;
    // printf("ans %d\n",ans) ;
    // printf("ans %d : %d %d\n",ans , C(n-1,m-1) , m * S(0,n-lm-1,m-2)) ;
    if(m % 2 == 1) {
        auto [l,r] = work(1 , lm - 1 , n) ;
        // printf("L %d %d : %d\n",l,r , (m-1)/2 - 1);
        ans = (ans + 1LL * m * S(l , r , (m-1)/2 - 1)) % mod;
        // printf("Ans %d\n",ans) ;
    }
    else {
        // k even
        if(n % 2 == 0) ans = (ans + 1LL * (m/2) * C(n/2 - 1 , m/2 - 1)) % mod;
        /// k odd
        int sol = 0;
        {
            auto [l,r] = work(1 , lm - 1 , n) ;
            sol = (1LL * (n - 2 - 1) * S(l , r , (m-2)/2 - 1) - 2LL * S2(l , r , (m-2)/2 - 1)%mod + mod) % mod;
        }
        auto [l,r] = work(lm , n , n) ;
        sol = (sol + 1LL * (2*lm-n+2 - 1) * S(l,r,(m-2)/2 - 1) + 2LL * S2(l,r,(m-2)/2 - 1)) % mod;
            // printf("sol %d , %d %d , %d %d\n",sol , l , r , S(l,r,1) , S2(l,r,1)) ;
        ans = (ans + 1LL * (m/2) * sol) % mod;
    }
    ans = 1LL * ans * qpow(m*2 , mod - 2) % mod;
    cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    init(10000003);
    int T;
    cin>>T;
    while(T--)Solve();
    return 0;
}