#include<cstdio>
using namespace std;
int T,n,m,pri[9999],cnt,pw[9999],v[9999];long long ans;
long long calc(int n,int a,int b,int c){
	if(!a||!n) return b/c*1ll*n;
	if(a>=c||b>=c) return calc(n,a%c,b%c,c)+b/c*1ll*n+a/c*(n*(n-1ll)/2);
	int t=(a*1ll*n+b)/c;
	return n*1ll*t-calc(t,c,c+a-b-1,a);
}
inline long long 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=(-b+a-1)/a;
		n-=tmp;b+=a*tmp;
	}
	return (n>0)?calc(n,a,b,c)+t*n:0;
}
void dfs(int nw,int a,int b,int coef){
	if(nw>cnt){
		for(int i=0,t1,t2;i<2;++i) for(int j=0;j<2;++j) if((i*a+j*b)%2==0){
			t1=(n-1)/a-i;t2=(n-1)*2/a-i;t1>>=1;t2>>=1;
			if(t1>=0) ans+=coef*(Calc(t1+1,a,(i*a-j*b)/2,b,j)-Calc(t1+1,-a,n-1-(i*a+j*b)/2,b,j));
			if(t2>=0) ans+=coef*Calc(t2+1,-a,n-1-(i*a+j*b)/2,b,j);
		}
		return;
	}
	for(int i=0,t=1;i<=pw[nw];++i,t*=pri[nw]){
		dfs(nw+1,a*t,b*v[nw]/t,coef);
		if(i<pw[nw]) dfs(nw+1,a*t*pri[nw],b*v[nw]/t,-coef);
	}
}
int main(){
	for(scanf("%d",&T);T--;printf("%lld\n",ans),ans=cnt=0){
		scanf("%d%d",&n,&m);
		for(int i=2;i*i<=m;++i) if(m%i==0){
			pri[++cnt]=i;pw[cnt]=0;v[cnt]=1;
			for(;m%i==0;m/=i) ++pw[cnt],v[cnt]*=i;
		}
		if(m>1) pri[++cnt]=m,pw[cnt]=1,v[cnt]=m;
		dfs(1,1,1,1);
	}
	return 0;
}