#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define output(v) for(auto&it:v){cout<<it<<" ";}cout<<"\n"
#define input(v) for(auto&it:v){cin>>it;}

void FastCode()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
ll gcd(ll a , ll b){
    if(!min(a,b)) return max(a,b);
    else return gcd(b,a%b);
}
void solve(){
    ll n ,a;
    cin >>n >> a;
    ll b = n;
    while( gcd(b,a) > 1)b--;
    cout<<b<<"\n";
}
int main(){
    FastCode();
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}