#include <bits/stdc++.h>
using namespace std;
#define maxn 10000010
#define mod 1000000007

int prime[maxn],pt=0;
bool vp[maxn];
int phi[maxn];
void SieveInit(const int N){
	phi[1]=1;
	for(int i=2;i<=N;i++){
		if(!vp[i])prime[++pt] = i, phi[i] = i-1;
		for(int j=1;j<=pt&&i*prime[j]<=N;j++){
			vp[i*prime[j]] = true;
			if(i%prime[j]==0){
				phi[i*prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i*prime[j]] = phi[i] * (prime[j]-1);
		}
	}
}
int fac[maxn],inv[maxn],inv_fac[maxn];
void FacInit(int N){
	fac[0]=inv_fac[0]=inv[1]=1;
	for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=N;i++)inv_fac[i]=1ll*inv_fac[i-1]*inv[i]%mod;
}
int Binom(int x,int y){
	if(y<0||x<y)return 0;
	return 1ll*fac[x]*inv_fac[y]%mod*inv_fac[x-y]%mod;
}
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
void dec(int &x,int y){x=(x-y<0?x-y+mod:x-y);}
int add(int x){return x>=mod?x-mod:x;}
int dec(int x){return x<0?x+mod:x;}
int ksm(int x,int y){
	int re=1;
	for(;y;y>>=1){
		if(y&1)re=1ll*re*x%mod;
		x=1ll*x*x%mod;
	}
	return re;
}

int main()
{
	SieveInit(maxn-10);
	FacInit(maxn-10);
	int Te;cin>>Te;while(Te--){
		int n,m;
		cin>>n>>m;
		int ans=0;
		auto calc=[&](int x,int y){
			return Binom(x-1,y-1);
		};
		auto solve=[&](int d){
			if(n%(m/d))return;
			int N = n / (m/d);
			// printf("solve : %d %d %d %d\n", d, N, calc(N,d), phi[m/d]);
			add(ans, 1ll*calc(N, d) * phi[m/d]%mod);
			return;
		};
		for(int i=1;i*i<=m;i++)
			if(m%i==0){
				solve(i);
				if(i*i != n)solve(m/i);
			}
		int p = (n-1)/2;
		dec(ans, 1ll*m * calc(n-p, m) %mod);
		
		if(m%2==1){
			if(n&1){ 
				// printf("ans : %d -> ",ans);
				add(ans, 1ll*calc(n/2, m/2) * m%mod);
				// printf("%d -> ",ans);
				add(ans, 1ll*calc(n/2, m/2+1) * m%mod);
				// printf("%d -> ",ans);
				
				dec(ans, 1ll*calc(n/2/2, m/2) * m%mod);
				// printf("%d -> ",ans);
				dec(ans, 1ll*calc(n/2/2, m/2+1) * m%mod);
				// printf("%d\n",ans);
			}
			else{
				add(ans, 1ll*calc(n/2, m/2+1) * m%mod);
				
				dec(ans, 1ll*calc(n/2/2, m/2+1) * m%mod);
				dec(ans, 1ll*calc(n/2/2, m/2) * m%mod);
			}
		}else{
			if(n%2==0)add(ans, 1ll*calc(n/2, m/2) * (m/2)%mod);
			for(int i=0;i<2;i++)
				for(int j=0;j<2;j++)
					if((n-i-j)%2==0){
						add(ans, 1ll*calc((n-i-j)/2,m/2+1) * (m/2)%mod);
						if(i)add(ans, 1ll*calc((n-i-j)/2,m/2) * (m/2)%mod);
						if(j)add(ans, 1ll*calc((n-i-j)/2,m/2) * (m/2)%mod);
						if(i&&j)add(ans, 1ll*calc((n-i-j)/2,m/2-1) * (m/2)%mod);
						
						if(!i && !j){
							dec(ans, 2ll*calc((n-i-j)/2/2,m/2+1) * (m/2)%mod);
							dec(ans, 4ll*calc((n-i-j)/2/2,m/2) * (m/2)%mod);
						}else if(i && j){
							dec(ans, 2ll*calc((n-i-j)/2/2,m/2+1) * (m/2)%mod);
							dec(ans, 4ll*calc((n-i-j)/2/2,m/2) * (m/2)%mod);
							dec(ans, 2ll*calc((n-i-j)/2/2,m/2-1) * (m/2)%mod);
						}else{
							dec(ans, 1ll*calc((n-i-j)/2/2,m/2+1) * (m/2)%mod); // 1 + n/2 , 0
							dec(ans, 1ll*calc((n-i-j)/2/2,m/2) * (m/2)%mod);
							
							dec(ans, 1ll*calc((n-i-j)/2/2,m/2+1) * (m/2)%mod);// 0 + n/2 , 1
							dec(ans, 1ll*calc((n-i-j)/2/2,m/2) * (m/2)%mod);
							dec(ans, 1ll*calc((n-i-j)/2/2,m/2-1) * (m/2)%mod);
						}
					}
		}
		
		ans=1ll*ans*ksm(2*m,mod-2)%mod;
		cout<<ans<<'\n';
	}
}
/*
1
7 4
*/