#include<bits/stdc++.h>
using namespace std;
int p[40],c[40],e;
void fj(int n){
    e=0;
    for(int i=2;i*i<=n;i++)if(!(n%i)){
        p[++e]=i,c[e]=0;
        while(!(n%i))n/=i,c[e]++;
    }
    if(n>1)p[++e]=n,c[e]=1;
}
#define ll long long
__int128 ans;
ll n,m;
ll sq(ll a,ll b){if(a<=0)return a/b;return (a-1)/b+1;}
ll xq(ll a,ll b){if(a<0)return (a-1)/b+1;return a/b;}
struct nn{ll a,b,c;};
nn operator + (const nn &x,const nn &y){
    return (nn){x.a+y.a,x.b+y.b,x.c+y.c+x.a*y.b};
}
nn qpow(nn a,ll b){
	nn c=(nn){0,0,0};
	for(;b;b>>=1){
		if(b&1)c=c+a;
		a=a+a;
	}
	return c;
}
nn F(ll a,ll b,ll c,ll n,nn x,nn y){
	if(!n){return (nn){0,0,0};}
	if(a>=c)return F(a%c,b,c,n,x,qpow(x,a/c)+y);
	ll cz=(a*n+b)/c;
	if(!cz)return qpow(y,n);
	return qpow(y,(c-b-1)/a)+x+F(c,(c-b-1)%a,a,cz-1,y,x)+qpow(y,n-(c*cz-b-1)/a);
}
ll vp(ll a,ll b,ll n,ll c){
    if(a>b)swap(a,b);
    if(!n)b=0;else b=(b-a)/n;
    swap(a,b);
    nn fk=qpow({1,0,0},b/c)+F(a,b%c,c,n,{1,0,0},{0,1,0});
    return fk.c+b/c;
}
ll calc(ll a,ll b){
    ll s=0;
    ll o=b;if(!(o&1))o/=2;
    s-=(n-1)/o+1;
    //o|i,i<n
    for(int c=0;c<2;c++)for(int d=0;d<2;d++){
        if((c*a+d*b)%2)continue;
        ll N=(n-1)*2-b*d-c*a,M=a*c-d*b;
        if(N<0)continue;N/=2,M/=2;
        ll bl=sq(M,b),br=N/b;
        ll tz=xq(N+M,b*2);
        s+=br-bl+1;
        if(tz>=bl){
            ll e=min(br,tz);
            s+=vp(b*bl-M,b*e-M,e-bl,a);
        }
        if(tz<br)tz=max(tz+1,bl),s+=vp(N-b*tz,N-b*br,br-tz,a);
    }
    return s;
    //a|y-x,b|y+x
}
void dfs(int x,int z1,int z2,int t){
    if(x==e+1){ans+=calc(z2,m/z1)*t;return;}
    int o=1;
    for(int i=0;i<=c[x];i++){
        if(i)o*=p[x];
        dfs(x+1,z1*o,z2*o,t);
        if(i<c[x])dfs(x+1,z1*o,z2*o*p[x],-t);
    }
}
void sol(){
    e=0;
    scanf("%lld%lld",&n,&m);fj(m);
    ans=0,dfs(1,1,1,1),printf("%lld\n",(long long)ans);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}