#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

using namespace std;

const ll inf = 1LL<<30;
const ll mod = 1e9+7;

int p,q;
int factorize(int n)
{
    int i,cnt=1,mx=0;
    for(i=2;i*i<n;i++)
    {
        if(n%i==0)
        {
            if(i%q!=0)
            {
                mx=max(mx,i);
            }
            if((n/i)%q!=0)
            {
                mx=max(mx,n/i);
            }
        }
    }
    if(n%i==0&&i%q!=0)
    {
        mx=max(mx,i);
    }

    if(n%q!=0)
    {
        mx=max(mx,n);
    }
    cout<<mx<<endl;
    return cnt;
}

int main(){
    IO;
    int t;
    cin>>t;
    while(t--)
    {
        cin>>p>>q;
        factorize(p);
    }
}