#include<iostream>

long long gcd(long long a, long long b) { return !b? a: gcd(b, a % b); }

using namespace std;

int main() {

    int TC = 1; cin >> TC;
    while(TC--) {

        long long n, a; cin >> n >> a;

        while(gcd(a, n) != 1) n--;

        cout << n << "\n";

    }

    return 0;

}