#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int a,b;
    cin >> a >> b;
    int ans = 0;
    for(int l = 1,r;l <= a;l = r + 1){
        r = a / (a / l);
        int k = a / l + 1;
        int l1 = b / k,r1 = b / (k + 1);
        //cout << l << " " << r << " " << l1 << " " << r1 << "\n";
        if(r1 >= l)ans = max(ans,r1);
        if(a % (a / l) == 0 && l1 >= r)ans = max(ans,r);
    }
    cout << ans << "\n";
    return;
}

signed main() {
    int T;
    cin >> T;
    while(T--)solve();
    return 0;
}