// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
ll func(ll a,ll b,ll c,ll N){
    if(!a)return b/c*(N+1);
    if(a>=c||b>=c)
    return (a/c)*N*(N+1)/2+(b/c)*(N+1)+func(a%c,b%c,c,N);
    ll M=(a*N+b)/c;
    return N*M-func(c,c-b-1,a,M-1);
}
ll calc(int n,int a,int b,int c,int t){
	if(a<0)b+=(n-1)*a,a=-a;
	if(b<0){
		if(!a)return 0;
		int tmp=(a-b-1)/a;
		n-=tmp,b+=a*tmp;
	}
	return (n>0)?func(a,b,c,n-1)+t*n:0;
}
vector<array<int,3>>pr;
int n,m;
ll ans=0;
void dfs(int u,int a,int b,int qwq){
	if(u>=SZ(pr)){
		ll res=0;
		F(c,0,1)F(d,0,1)if(!((c*a+b*d)&1)){
			int x=((n-1)/a-c)>>1,y=(((n-1)<<1)/a-c)>>1;
			if(x>=0)res+=calc(x+1,a,(c*a-b*d)>>1,b,d)-calc(x+1,-a,n-1-((a*c+b*d)>>1),b,d);
			if(y>=0)res+=calc(y+1,-a,n-1-((c*a+b*d)>>1),b,d);
		}
		ans+=1ll*qwq*res;
		return;
	}
	int t=1,val=pr[u][2];
	F(i,0,pr[u][1]){
		dfs(u+1,a*t,b*val/t,qwq);
		if(i<pr[u][1])dfs(u+1,a*t*pr[u][0],b*val/t,-qwq);
		t*=pr[u][0];
	}
}
void solve(){
	n=read(),m=read(),pr.clear(),ans=0;
	F(i,2,sqrt(m))if(m%i==0){
		int cnt=0,val=1;
		for(;m%i==0;m/=i)++cnt,val*=i;
		pr.push_back({i,cnt,val});
	}
	if(m>1)pr.push_back({m,1,m});
	dfs(0,1,1,1),cout<<ans<<endl;
}
signed main(){
	const int zsy=read();
	F(____,1,zsy)solve();
}