#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p1 first #define p2 second #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e7+10; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int P,r,b[maxn],pr[maxn],ct; void init(){ up(i,2,1e7){ if(!b[i])pr[++ct]=i; up(j,1,ct){ if(i*pr[j]>1e7)break; b[i*pr[j]]=1; if(!(i%pr[j]))break; } } } int calc(int x,int y){ if((x-1)%4==0){ if(y)return x-1; else return 2*x-1; }if(y)return x+1; return 1; } void slv(){ P=read(),r=read(); /*up(i,0,P-1)f[i]=0; up(i,0,P-1)f[i*1ll*i%P]++; ll res=0; up(i,0,P-1)res+=f[i]*1ll*f[(r-i+P)%P];*/ ll res=1; for(int j=1;j<=ct&&pr[j]*pr[j]<=P;++j){ if(!(P%pr[j]))P/=pr[j],res=res*1ll*calc(pr[j],r%pr[j]); }if(P!=1)res=res*1ll*calc(P,r%P); printf("%lld\n",res); }int main(){ init(); int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; }