#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define INF INT_MAX
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define nl "\n"
using namespace std;
const ll MOD  = 1e9+7;
const int mxN = 2e5+1;


int main()
{
    FAST
    //==================
    ll t; cin >> t;
    while(t--){
        ll n , a ; cin >> n>> a;
        ll k = a ;
        map<int,int> m;
        for(int i=2;i*i<=k;i++){
            if(k%i == 0){
                m[i]++;
                while(k%i==0)k/=i;
            }
        }
        if(k>1)m[k]++;
        ll b = a*(n/a);
        if(b == n)b-=a;
        for(ll p =  n; p>b;p--){
            ll s= p;
            bool is =1;
            for(int j=2;j*j<=s;j++){
                if(s%j==0){
                    if(m[j]){
                        is =0;
                        break;
                    }else{
                        while(s%j==0)s/=j;
                    }
                }
            }
            if(s > 1){
                if(m[s])continue;
            }
            if(!is)continue;
            cout << p << nl;
            break;
        }

    }



}