#include <bits/stdc++.h>
using namespace std;
template <typename T>
void spit(vector<T> a) {
  for (auto i : a) cout << i << " ";
  cout << "\n";
}
template <typename T>
void maxa(T& a, T b) {
  a = max(a, b);
}
template <typename T>
void mina(T& a, T b) {
  a = min(a, b);
}
int nxt() {
  int a;
  cin >> a;
  return a;
}
long long int nxtll() {
  long long int a;
  cin >> a;
  return a;
}
vector<pair<long long int, long long int> > tempa, result;
vector<pair<long long int, long long int> > factorize(long long int a) {
  vector<pair<long long int, long long int> > answer;
  for (long long int i = 2; i * i <= a; i++) {
    if (a % i == 0) {
      long long int count = 0;
      while (a % i == 0) {
        count++;
        a /= i;
      }
      answer.push_back(make_pair(i, count));
    }
  }
  if (a != 1) {
    answer.push_back(make_pair(a, 1));
  }
  return answer;
}
long long int analyze(long long int a) {
  long long int x = a;
  result.clear();
  for (auto i : tempa) {
    if (x % i.first == 0) {
      long long int count = 0;
      while (x % i.first == 0) {
        count++;
        x /= i.first;
      }
      result.push_back(make_pair(i.first, count));
    } else {
      result.push_back(make_pair(i.first, 0));
    }
  }
  return x;
}
long long int bahu(long long int a, long long int b) {
  long long int answer = 1LL;
  long long int base = a;
  while (b) {
    if (b % 2 == 0) {
      base = base * base;
      b /= 2LL;
    } else {
      answer *= base;
      b--;
    }
  }
  return answer;
}
long long int sheldon(vector<pair<long long int, long long int> >& a) {
  long long int answer = bahu(a[0].first, a[0].second);
  for (auto i : a) {
    answer = min(answer, bahu(i.first, i.second));
  }
  return answer;
}
void solve() {
  tempa.clear();
  result.clear();
  long long int a, b;
  cin >> a >> b;
  if (b > a) {
    cout << a << endl;
    return;
  }
  tempa = factorize(b);
  long long int answer = analyze(a);
  vector<pair<long long int, long long int> > pika;
  for (int(i) = 0; (i) < (tempa.size()); (i)++) {
    if (tempa[i].second > result[i].second) {
      cout << a << endl;
      return;
    }
    pika.push_back(
        make_pair(tempa[i].first, result[i].second - tempa[i].second + 1LL));
  }
  cout << a / sheldon(pika) << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  bool multi_run = 1;
  if (multi_run) {
    int t;
    cin >> t;
    while (t--) solve();
  } else {
    solve();
  }
}
