#include<bits/stdc++.h>
#define li long long
#define l_l long long
using namespace std;
const li i_1=1;
const l_l i_2=1;
inline l_l xqz(l_l a,l_l b){
	return (a-(a%b+b)%b)/b;
}
li di(l_l a,l_l b,l_l c,l_l n){
	if(n==0)return xqz(b,c);
	l_l am=a%c+c,bm=b%c+c;
	if(am>=c)am-=c;
	if(bm>=c)bm-=c;
	if(a==am&&b==bm){
		if(a==0)return 0;
		l_l m=(i_1*a*n+b)/c;
		return i_1*n*m-di(c,c-b-1,a,m-1);
	}
	l_l ay=(a-am)/c,by=(b-bm)/c;
	li ans=i_1*n*(n+1)/2*ay+i_1*(n+1)*by;
	return ans+di(am,bm,c,n);
}
inline li d(l_l a,l_l b,l_l c,l_l n){
	return di(a,b,c,n)-xqz(b,c);
}
l_l gcd(l_l a,l_l b){
	return b==0?a:gcd(b,a%b);
}
l_l lcm(l_l a,l_l b){
	return a/gcd(a,b)*b;
}
li f(l_l a,l_l b,l_l n){
	--n;
	if(n==1)return (a==1&&b==1);
	l_l L,R;
	li ans=n/lcm(a,b);
	if((a&1)){
		l_l ll,rr;
		if((b&1)){
			L=1/a+1,R=(n+1)/a;
			ll=(L-1)/2+1,rr=R/2;
			if(ll<=rr)ans+=d(2*a,-2,2*b,rr)-d(2*a,-2,2*b,ll-1);
			ll=L/2,rr=(R+1)/2-1;
			if(ll<=rr)ans+=d(2*a,a+b-2,2*b,rr);
			if(ll<=rr)ans-=d(2*a,a+b-2,2*b,ll-1);
			L=(n+1)/a+1,R=2*n/a;
			ll=(L-1)/2+1,rr=R/2;
			if(ll<=rr)ans+=d(-2*a,2*n,2*b,rr)-d(-2*a,2*n,2*b,ll-1);
			ll=L/2,rr=(R+1)/2-1;
			if(ll<=rr)ans+=d(-2*a,2*n+b-a,2*b,rr);
			if(ll<=rr)ans-=d(-2*a,2*n+b-a,2*b,ll-1);
			return ans;
		}else{
			L=1/a+1,R=(n+1)/a;
			ll=(L-1)/2+1,rr=R/2;
			if(ll<=rr)ans+=d(2*a,-2,b,rr)-d(2*a,-2,b,ll-1);
			L=(n+1)/a+1,R=2*n/a;
			ll=(L-1)/2+1,rr=R/2;
			if(ll<=rr)ans+=d(-2*a,2*n,b,rr)-d(-2*a,2*n,b,ll-1);
			return ans;
		}
	}else{
		if((b&1)){
			L=1/a+1,R=(n+1)/a;
			if(L<=R)ans+=d(a,-2,2*b,R)-d(a,-2,2*b,L-1);
			L=(n+1)/a+1,R=2*n/a;
			if(L<=R)ans+=d(-a,2*n,2*b,R)-d(-a,2*n,2*b,L-1);
			return ans;
		}else{
			L=1/a+1,R=(n+1)/a;
			if(L<=R)ans+=d(a,-2,b,R)-d(a,-2,b,L-1);
			L=(n+1)/a+1,R=2*n/a;
			if(L<=R)ans+=d(-a,2*n,b,R)-d(-a,2*n,b,L-1);
			return ans;
		}
	}
	return -1;
}
const int A=35000;
const int B=12;
int s[A+5],dd[A+5],tt=0;
int n,m,pr[B+5],zs[B+5],gs;
int xa[B+5],xb[B+5];
l_l ans;
void print(){
	s[1]=1;
	for(int i=2;i<=A;++i){
		if(!s[i])dd[++tt]=i;
		for(int j=1;j<=tt&&i*dd[j]<=A;++j){
			s[i*dd[j]]=1;
			if(i%dd[j]==0)break;
		}
	}
}
void dfs(int stp){
	if(stp>gs){
		int r=1;
		l_l l1=1,l2=1;
		for(int i=1;i<=gs;++i){
			for(int j=1;j<=xa[i];++j)l1*=pr[i];
			for(int j=1;j<=xb[i];++j)l2*=pr[i];
			if(xa[i]+xb[i]!=zs[i])r=-r;
		}
		ans+=r*f(l1,l2,n);
		return;
	}
	for(int i=0;i<=zs[stp];++i)
		for(int j=zs[stp]-i;j<=zs[stp]-i+1;++j){
			if(j>zs[stp])break;
			xa[stp]=i,xb[stp]=j;
			dfs(stp+1);
		}
}
signed main(){
	print();
	int T;
	cin>>T;
	while(T--){
		gs=0;
		cin>>n>>m;
		for(int i=1;i<=tt;++i)if(m%dd[i]==0){
			pr[++gs]=dd[i];
			zs[gs]=1;
			m/=dd[i];
			while(m%dd[i]==0)++zs[gs],m/=dd[i];
		}
		if(m!=1){
			pr[++gs]=m;
			zs[gs]=1;
		}
		ans=0;
		dfs(1);
		printf("%lld\n",ans);
	}
	return (signed)0;
}