#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
 
        int chosen = 1;
        for (int i = 1; i * i <= n; ++i) {
            if (n % i == 0) {
                if (i <= k) chosen = max(chosen, i);
                int j = n / i;
                if (j <= k) chosen = max(chosen, j);
            }
        }
 
        cout << n / chosen << '\n';
    }
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwoKaW50MzJfdCBtYWluKCkgewogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBpbnQgbiwgazsKICAgICAgICBjaW4gPj4gbiA+PiBrOwoKICAgICAgICBpbnQgY2hvc2VuID0gMTsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSAqIGkgPD0gbjsgKytpKSB7CiAgICAgICAgICAgIGlmIChuICUgaSA9PSAwKSB7CiAgICAgICAgICAgICAgICBpZiAoaSA8PSBrKSBjaG9zZW4gPSBtYXgoY2hvc2VuLCBpKTsKICAgICAgICAgICAgICAgIGludCBqID0gbiAvIGk7CiAgICAgICAgICAgICAgICBpZiAoaiA8PSBrKSBjaG9zZW4gPSBtYXgoY2hvc2VuLCBqKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgY291dCA8PCBuIC8gY2hvc2VuIDw8ICdcbic7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=

NQo4IDcKOCAxCjYgMTAKOTk5OTk5NzMzIDk5OTk5OTczMgo5OTk5OTk3MzMgOTk5OTk5NzMzCgoKCg==

5
8 7
8 1
6 10
999999733 999999732
999999733 999999733