/**
 *    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 ans = 1;
        for (int64_t i = n; i >= max(n - 100, (int64_t)1); --i) {
            if (a * i / (gcd(a, i) * gcd(a, i)) >= a * ans / (gcd(a, ans) * gcd(a, ans))) {
                ans = i;
            }
        }
        cout << ans / gcd(a, ans) << "\n";
    }
}