#include<bits/stdc++.h>
////#include "cmake-build-debug/Car.h"
using namespace std;
#define endl         '\n'
#define ll           long long
const int N = 2e5 + 5 ;
void fast() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
}
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int main() {
    fast() ;
    int t ;
    cin>>t ;
    while (t--)
    {
        ll a,n ;
        cin>>n>>a ;
        ll ans = 0 ;
        for (ll b =n ;;b--)
        {
            if (gcd(a,b) == 1 )
            {
                ans = b ;
                break ;
            }
        }
        cout << ans << endl ;
    }
    return  0 ;
}