#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);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBJTyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApLGNpbi50aWUoMCksY291dC50aWUoMCk7Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgbGwgaW5mID0gMUxMPDwzMDsKY29uc3QgbGwgbW9kID0gMWU5Kzc7CgppbnQgcCxxOwppbnQgZmFjdG9yaXplKGludCBuKQp7CiAgICBpbnQgaSxjbnQ9MSxteD0wOwogICAgZm9yKGk9MjtpKmk8bjtpKyspCiAgICB7CiAgICAgICAgaWYobiVpPT0wKQogICAgICAgIHsKICAgICAgICAgICAgaWYoaSVxIT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBteD1tYXgobXgsaSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYoKG4vaSklcSE9MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbXg9bWF4KG14LG4vaSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBpZihuJWk9PTAmJmklcSE9MCkKICAgIHsKICAgICAgICBteD1tYXgobXgsaSk7CiAgICB9CgogICAgaWYobiVxIT0wKQogICAgewogICAgICAgIG14PW1heChteCxuKTsKICAgIH0KICAgIGNvdXQ8PG14PDxlbmRsOwogICAgcmV0dXJuIGNudDsKfQoKaW50IG1haW4oKXsKICAgIElPOwogICAgaW50IHQ7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgY2luPj5wPj5xOwogICAgICAgIGZhY3Rvcml6ZShwKTsKICAgIH0KfQoK