#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<pair<lng,lng>,null_type,less<pair<lng,lng>>,rb_tree_tag,tree_order_statistics_node_update>
#define rtr return 0
#define lng int
#define endl "\n"
#define cmbntrcs for(int i=1;i<INF;i++){fact[i]=mul(i,fact[i-1]);inv[i]=mod_inv(fact[i]);}
#define nmbrthry
//#pragma GCC optimize
const int MOD=1e9+7,INF=1e6+7,SZ=2e5+7,MSZ=1e5+3;
int add(int x,int y){int z=x+y;if(z>=MOD){z-=MOD;}return z;}
int sub(int x,int y){int z=x-y;if(z<0){z+=MOD;}return z;}
int mul(int x,int y){return(x*1ll*y)%MOD;}
int pwr(int a,lng b)
{
 if(!b){return 1;}
 int res=pwr(a,b/2);res=mul(res,res);if(b%2){res=mul(res,a);}
 return res;
}
int mod_inv(int a){return pwr(a,MOD-2);}
vector<int>fact(INF,1),inv(INF,1);
int nCr(int n,int r){return mul(fact[n],mul(inv[r],inv[n-r]));}
int nPr(int n,vector<int>r)
{
 int den=1;
 for(int i=0;i<r.size();i++){den=mul(den,inv[i]);}
 return mul(fact[n],den);
}
int sb(int s,int b){return nCr(s+b-1,s);}
int prfx(int i,int j){if(i<0||j<0){return 0;}return nCr(i+j,i);}
lng lcm(lng x,lng y){return(x*y/__gcd(x,y));}
lng trig(lng x){return x*(x+1)/2;}
lng sigma(lng x,lng y){return trig(y)-trig(x-1);}
lng fp(lng a,lng b)
{
 if(!b){return 1;}
 lng res=fp(a,b/2);res*=res;if(b%2){res*=a;}
 return res;
}
string num_bin(lng n){if(n==0){return"0";}string x="";while(n){char c=(n%2)+'0';x+=c;n/=2;}reverse(x.begin(),x.end());return x;}
lng bin_num(string x){reverse(x.begin(),x.end());lng n=0;for(int i=0;i<x.size();i++){if(x[i]=='1'){n+=pow(2,i);}}return n;}
struct mtrx
{
 lng nx,mx;vector<vector<lng>>bd;
 void bld(vector<vector<lng>>obd){nx=obd.size(),mx=obd[0].size();bd=obd;}
 void outm(){for(lng i=0;i<nx;i++){for(lng j=0;j<mx;j++){cout << bd[i][j] << ' ';}cout << endl;}}
};
mtrx idnt(lng n)
{
 vector<vector<lng>>v;v.resize(n);
 for(lng i=0;i<n;i++){v[i].assign(n,0);v[i][i]=1;}
 return{n,n,v};
}
mtrx modn(mtrx a,lng x)
{
 for(lng i=0;i<a.nx;i++){for(lng j=0;j<a.mx;j++){a.bd[i][j]%=x;}}
 return a;
}
mtrx mulm(mtrx a,mtrx b)
{
 if(a.mx!=b.nx){return{1,1,{{0}}};}
 vector<vector<lng>>v;v.resize(a.nx);
 for(lng i=0;i<a.nx;i++)
 {
  v[i].resize(b.mx);
  for(lng j=0;j<b.mx;j++)
  {
   lng s=0;
   for(lng x=0;x<a.mx;x++)
   {
    s+=a.bd[i][x]*b.bd[x][j];
    s%=MOD;
   }
   v[i][j]=s;
  }
 }
 mtrx ret;ret.bld(v);
 //MOD FACTOR ret=modn(ret,MOD);
 return ret;
}
mtrx fpm(mtrx a,lng b)
{
 if(b==0){return idnt(a.nx);}
 mtrx ret=fpm(a,b/2);ret=mulm(ret,ret);
 if(b%2){ret=mulm(ret,a);}
 return ret;
}
lng rndm(lng a,lng b){return a+rand()%((b+1)-a);}
lng rnd_num(lng n)
{lng z=rndm(1,9);n--;while(n--){z*=10;z+=rndm(0,9);}return z;}
__int128 gcd(__int128 a,__int128 b)
{
 if(b==0){return a;}
 return gcd(b,a%b);
}
int main()
{
 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 lng tt;cin >> tt;
 while(tt--)
 {
  __int128 a,n,bst=0,ans=0,x=0;
  lng ina,inn,oans;cin >> inn >> ina;a=ina;n=inn;
  n++;
  do
  {
   n--;
   x=(a*n)/(gcd(a,n)*gcd(a,n));
   //cout << int64_t(n) << ' ' << int64_t(x) << endl;
   if(x>=bst){bst=x;ans=n;}
  }while(gcd(a,n)!=1);
  oans=ans;
  cout << oans << endl;
 }
 return 0;
}