#include <bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;
const long long inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int cnt;
long long p[100];
inline long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
inline long long fmul(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    b >>= 1;
    a = (a << 1) % mod;
  }
  return res;
}
inline long long qp(long long x, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = fmul(ans, x, mod);
    x = fmul(x, x, mod);
    p >>= 1;
  }
  return ans;
}
inline bool mr(long long x, long long b) {
  long long k = x - 1;
  while (k) {
    long long cur = qp(b, k, x);
    if (cur != 1 && cur != x - 1) return false;
    if ((k & 1) == 1 || cur == x - 1) return true;
    k >>= 1;
  }
  return true;
}
inline bool prime(long long x) {
  if (x == 46856248255981ll || x < 2) return false;
  if (x == 2 || x == 3 || x == 7 || x == 61 || x == 24251) return true;
  return mr(x, 2) && mr(x, 61);
}
inline long long f(long long x, long long c, long long n) {
  return (fmul(x, x, n) + c) % n;
}
inline long long PR(long long x) {
  long long s = 0, t = 0, c = rand() % (x - 1) + 1;
  int stp = 0, goal = 1;
  long long val = 1;
  for (goal = 1;; goal <<= 1, s = t, val = 1) {
    for (stp = 1; stp <= goal; ++stp) {
      t = f(t, c, x);
      val = fmul(val, abs(t - s), x);
      if ((stp % 127) == 0) {
        long long d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    long long d = gcd(val, x);
    if (d > 1) return d;
  }
}
inline void fac(long long x) {
  if (x < 2) return;
  if (prime(x)) {
    p[cnt++] = x;
    return;
  }
  long long p = x;
  while (p >= x) p = PR(x);
  while ((x % p) == 0) x /= p;
  fac(x), fac(p);
}
long long num[100];
long long n, m;
long long ans;
void dfs(int pos, long long sum) {
  if (pos == cnt) {
    if (sum % m != 0) ans = max(ans, sum);
    return;
  }
  dfs(pos + 1, sum);
  long long temp = 1;
  for (int i = 0; i < num[pos]; i++) {
    temp *= p[pos];
    dfs(pos + 1, sum * temp);
  }
}
long long mtt[N];
int main() {
  int T;
  cin >> T;
  while (T--) {
    ans = 0;
    cnt = 0;
    long long x;
    cin >> n >> m;
    if (m > n) {
      cout << n << endl;
      continue;
    }
    if (m < n && n % m != 0) {
      cout << n << endl;
      continue;
    }
    x = n;
    fac(m);
    sort(p, p + cnt);
    cnt = unique(p, p + cnt) - p;
    long long mi = x;
    for (int i = 0; i < cnt; i++) {
      int temp = 0;
      mtt[i] = 1;
      if (n % p[i]) {
        continue;
      }
      while (n % p[i] == 0) {
        n /= p[i];
        mtt[i] *= p[i];
      }
      long long mmt = 1;
      while (m % p[i] == 0) {
        m /= p[i];
        mmt *= p[i];
      }
      num[i] = temp;
      mi = min(mi, mtt[i] / (mmt / p[i]));
    }
    printf("%lld\n", x / mi);
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with t pairs of integers p_i and q_i and for each pair decided to find the greatest integer x_i, such that: 

  * p_i is divisible by x_i; 
  * x_i is not divisible by q_i. 

Oleg is really good at division and managed to find all the answers quickly, how about you?

Input

The first line contains an integer t (1 ≤ t ≤ 50) — the number of pairs.

Each of the following t lines contains two integers p_i and q_i (1 ≤ p_i ≤ 10^{18}; 2 ≤ q_i ≤ 10^{9}) — the i-th pair of integers.

Output

Print t integers: the i-th integer is the largest x_i such that p_i is divisible by x_i, but x_i is not divisible by q_i.

One can show that there is always at least one value of x_i satisfying the divisibility conditions for the given constraints.

Example

Input


3
10 4
12 6
179 822


Output


10
4
179

Note

For the first pair, where p_1 = 10 and q_1 = 4, the answer is x_1 = 10, since it is the greatest divisor of 10 and 10 is not divisible by 4.

For the second pair, where p_2 = 12 and q_2 = 6, note that 

  * 12 is not a valid x_2, since 12 is divisible by q_2 = 6; 
  * 6 is not valid x_2 as well: 6 is also divisible by q_2 = 6. 

The next available divisor of p_2 = 12 is 4, which is the answer, since 4 is not divisible by 6.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;
const long long inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int cnt;
long long p[100];
inline long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
inline long long fmul(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    b >>= 1;
    a = (a << 1) % mod;
  }
  return res;
}
inline long long qp(long long x, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = fmul(ans, x, mod);
    x = fmul(x, x, mod);
    p >>= 1;
  }
  return ans;
}
inline bool mr(long long x, long long b) {
  long long k = x - 1;
  while (k) {
    long long cur = qp(b, k, x);
    if (cur != 1 && cur != x - 1) return false;
    if ((k & 1) == 1 || cur == x - 1) return true;
    k >>= 1;
  }
  return true;
}
inline bool prime(long long x) {
  if (x == 46856248255981ll || x < 2) return false;
  if (x == 2 || x == 3 || x == 7 || x == 61 || x == 24251) return true;
  return mr(x, 2) && mr(x, 61);
}
inline long long f(long long x, long long c, long long n) {
  return (fmul(x, x, n) + c) % n;
}
inline long long PR(long long x) {
  long long s = 0, t = 0, c = rand() % (x - 1) + 1;
  int stp = 0, goal = 1;
  long long val = 1;
  for (goal = 1;; goal <<= 1, s = t, val = 1) {
    for (stp = 1; stp <= goal; ++stp) {
      t = f(t, c, x);
      val = fmul(val, abs(t - s), x);
      if ((stp % 127) == 0) {
        long long d = gcd(val, x);
        if (d > 1) return d;
      }
    }
    long long d = gcd(val, x);
    if (d > 1) return d;
  }
}
inline void fac(long long x) {
  if (x < 2) return;
  if (prime(x)) {
    p[cnt++] = x;
    return;
  }
  long long p = x;
  while (p >= x) p = PR(x);
  while ((x % p) == 0) x /= p;
  fac(x), fac(p);
}
long long num[100];
long long n, m;
long long ans;
void dfs(int pos, long long sum) {
  if (pos == cnt) {
    if (sum % m != 0) ans = max(ans, sum);
    return;
  }
  dfs(pos + 1, sum);
  long long temp = 1;
  for (int i = 0; i < num[pos]; i++) {
    temp *= p[pos];
    dfs(pos + 1, sum * temp);
  }
}
long long mtt[N];
int main() {
  int T;
  cin >> T;
  while (T--) {
    ans = 0;
    cnt = 0;
    long long x;
    cin >> n >> m;
    if (m > n) {
      cout << n << endl;
      continue;
    }
    if (m < n && n % m != 0) {
      cout << n << endl;
      continue;
    }
    x = n;
    fac(m);
    sort(p, p + cnt);
    cnt = unique(p, p + cnt) - p;
    long long mi = x;
    for (int i = 0; i < cnt; i++) {
      int temp = 0;
      mtt[i] = 1;
      if (n % p[i]) {
        continue;
      }
      while (n % p[i] == 0) {
        n /= p[i];
        mtt[i] *= p[i];
      }
      long long mmt = 1;
      while (m % p[i] == 0) {
        m /= p[i];
        mmt *= p[i];
      }
      num[i] = temp;
      mi = min(mi, mtt[i] / (mmt / p[i]));
    }
    printf("%lld\n", x / mi);
  }
  return 0;
}

```