#include<bits/stdc++.h> #define int long long #define p1(x) ((x).first) #define p2(x) ((x).second) #pragma GCC optimize(3) using namespace std; bitset<10003000>p; vector<int>pfac[10000300]; inline int f(int p,int r){ if((p-1)%4==0){ if(!r)return 2*p-1; else return p-1; } if(!r)return 1; else return p+1; } vector<int>P; inline void init(){ p.set(); p[1]=0; for(int i=2;i<=1e7;i++) if(p[i]){ for(int j=2*i;j<=1e7;j+=i) p[j]=0; P.push_back(i); } } signed main(){ // freopen("rainbow.in","r",stdin); // freopen("rainbow.out","w",stdout); ios::sync_with_stdio(0); init(); int t; cin>>t; while(t--){ int n,r; cin>>n>>r; int res=1; for(int p:P){ if(p*p>n)break; if(n%p==0){ n/=p; res=res*f(p,r%p); } } if(n!=1)res=res*f(n,r%n); cout<<res<<endl;; } cout.flush(); return 0; }