# pragma GCC optimize (2)
# pragma GCC optimize (3)
# pragma GCC target ("avx")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("inline")
# pragma GCC optimize ("-fgcse")
# pragma GCC optimize ("-fgcse-lm")
# pragma GCC optimize ("-fipa-sra")
# pragma GCC optimize ("-ftree-pre")
# pragma GCC optimize ("-ftree-vrp")
# pragma GCC optimize ("-fpeephole2")
# pragma GCC optimize ("-ffast-math")
# pragma GCC optimize ("-fsched-spec")
# pragma GCC optimize ("unroll-loops")
# pragma GCC optimize ("-falign-jumps")
# pragma GCC optimize ("-falign-loops")
# pragma GCC optimize ("-falign-labels")
# pragma GCC optimize ("-fdevirtualize")
# pragma GCC optimize ("-fcaller-saves")
# pragma GCC optimize ("-fcrossjumping")
# pragma GCC optimize ("-fthread-jumps")
# pragma GCC optimize ("-funroll-loops")
# pragma GCC optimize ("-fwhole-program")
# pragma GCC optimize ("-freorder-blocks")
# pragma GCC optimize ("-fschedule-insns")
# pragma GCC optimize ("inline-functions")
# pragma GCC optimize ("-ftree-tail-merge")
# pragma GCC optimize ("-fschedule-insns2")
# pragma GCC optimize ("-fstrict-aliasing")
# pragma GCC optimize ("-fstrict-overflow")
# pragma GCC optimize ("-falign-functions")
# pragma GCC optimize ("-fcse-skip-blocks")
# pragma GCC optimize ("-fcse-follow-jumps")
# pragma GCC optimize ("-fsched-interblock")
# pragma GCC optimize ("-fpartial-inlining")
# pragma GCC optimize ("no-stack-protector")
# pragma GCC optimize ("-freorder-functions")
# pragma GCC optimize ("-findirect-inlining")
# pragma GCC optimize ("-fhoist-adjacent-loads")
# pragma GCC optimize ("-frerun-cse-after-loop")
# pragma GCC optimize ("inline-small-functions")
# pragma GCC optimize ("-finline-small-functions")
# pragma GCC optimize ("-ftree-switch-conversion")
# pragma GCC optimize ("-foptimize-sibling-calls")
# pragma GCC optimize ("-fexpensive-optimizations")
# pragma GCC optimize ("-funsafe-loop-optimizations")
# pragma GCC optimize ("inline-functions-called-once")
# pragma GCC optimize ("-fdelete-null-pointer-checks")

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
  
#define mod 1000000007
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
    bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
  
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
    if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
    int m=iv.size(); ++n;
    if(m>=n)return;
    iv.resize(n),fac.resize(n),ifac.resize(n);
    For(i,m,n-1){
        iv[i]=iv[mod%i]*(mod-mod/i);
        fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
    }
}
inline modint C(int n,int m){
    if(m<0||n<m)return 0;
    return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
  
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
  
#define maxn 10000005
#define inf 0x3f3f3f3f
  
int n,m,g;
bool vis[maxn];
int pri[maxn],tot,phi[maxn],mnp[maxn];
void prework(int n)
{
    vis[1]=1;phi[1]=1;
    For(i,2,n){
        if(!vis[i])pri[++tot]=i,phi[i]=i-1,mnp[i]=i;
        For(j,1,tot){
            if(i*pri[j]>n)break;
            int x=i*pri[j];
            vis[x]=1; mnp[x]=pri[j];
            if(i%pri[j])phi[x]=phi[i]*(pri[j]-1);
            else {phi[x]=phi[i]*pri[j];break;}
        }
    }
}
  
int p[233333],pc[233333],cnt;
void getfac(int n){
    cnt=0;
    while(n>1){
        int i=mnp[n];
        p[++cnt]=i;pc[cnt]=0;
        while(n%i==0)n/=i,pc[cnt]++;
    }
}
  
modint res=0;
  
modint calc(int x)
{
    int n=::n/x;
    int m=::m/x;
   //  cout<<x<<" "<<phi[x]<<' '<<(C(n-1,m-1) - C(n-(n+1)/2,m-1)*m).x<<endl;
    if(x>1) return C(n-1,m-1);
    return C(n-1,m-1) - C(n-(n+1)/2,m-1)*m;
}
  
void dfs(int u,int now)
{
    if(u==cnt+1) return res+=phi[now]*calc(now),void();
    dfs(u+1,now);
    For(i,1,pc[u]) now*=p[u],dfs(u+1,now);
}
  
void work()
{
    n=read(),m=read(),g=__gcd(n,m);
    getfac(g);
    res=0;
    dfs(1,1);
//   cout<<"res "<<res.x<<endl;
    if(m%2==0){
        int lim=(n-1)/2;
        for(int i=0;i<=n;i+=2){
            int dan=n-i;
            int L=max(1,dan-lim);
            int R=min(lim,dan-1);
            if(L>R)continue;
            int tmp=R-L+1;
            res+=(m/2)*C(i/2-1,m/2-2)*tmp;
        }
        if(n%2==0)res+=C(n/2-1,m/2-1)*(m/2);
    }else{
        For(i,1,(n-1)/2)
            if((n-i)%2==0)res+=C((n-i)/2-1,m/2-1)*m;
    }
    res/=(2*m);
    printf("%d\n",res.x);
}
  
/*
9 3
5 3
  
2 3 4 (6)
1 4 4 (3)
3 3 3 (1)
  
2 3 4
3 2 4
1 4 4
3 3 3
  
2 3 4
  
*/
  
signed main()
{
    prework(1e7);
    initC(1e7);
    ;int T=read();
    while(T--)work();
    return 0;
}
  
/*
.... .... ....
*/
  
/*
  
$n,m$
  
$ C(n-1,m-1) - \sum_{i=(n+1)/2}^{n-(m-1)} C(n-i-1,m-2)*m $
  
$ C(n-1,m-1) - m * C()$
  
*/