/**
 *    author:  MaGnsi0
 *    created: 21.04.2022 11:34:21
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int64_t n, a;
        cin >> n >> a;
        int64_t b = 1;
        for (int64_t i = n; i >= max(n - 100, (int64_t)1); --i) {
            if (a * i / (gcd(a, i) * gcd(a, i)) >= a * b / (gcd(a, b) * gcd(a, b))) {
                b = i;
            }
        }
        cout << b / gcd(a, b) << "\n";
    }
}