#include<bits/stdc++.h>

using namespace std;

#define fast ios::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);

typedef long long ll;

const ll N = 100111, MOD = 1e9 + 7;

ll t, n, a;

int main()
{
    scanf("%I64d", &t);
    while(t--)
    {
        scanf("%I64d%I64d", &n, &a);
        ll ans = 0;
        ll ansB = n;
        for(ll b = n; b > max(n - 1500, 1ll); b--)
        {
            ll g = __gcd(a, b);
            if((a * b) / (g * g) >= ans)
            {
                ans = (a * b) / (g * g);
                ansB = b;
            }
            if(g == 1) break;
        }
        printf("%I64d\n", ansB);
    }
}