CF1444A WA

// Problem: A. Division
// Contest: Codeforces - Codeforces Round 680 (Div. 1, based on Moscow Team Olympiad)
// URL: https://codeforces.com/problemset/problem/1444/A
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    int t;
    ll p, q;
    cin >> t;
    while (t--) {
        cin >> p >> q;
        if (p % q) {
            cout << p << endl;
        } else {
            ll ans = 1;
            for (ll i = 2; i * i <= q; ++i) {
                if (q % i == 0) {
                    ans = max(ans, p / (q / i));
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
};