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.
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
    ans = 1
    for i in range(1, x+1): ans = (ans * i) % mod
    return ans
def arr2D(n, m, default=0): return [[default for j in range(m)] for i in range(n)]
def arr3D(n, m, r, default=0): return [[[default for k in range(r)] for j in range(m)] for i in range(n)]
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}
class DSU:
    def __init__(self, length): self.length = length; self.parent = [-1] * self.length  # O(log(n))
    def getParent(self, node, start):  # O(log(n))
        if node >= self.length: return False
        if self.parent[node] < 0:
            if start != node: self.parent[start] = node
            return node
        return self.getParent(self.parent[node], start)
    def union(self, node1, node2):  # O(log(n))
        parent1 = self.getParent(node1, node1); parent2 = self.getParent(node2, node2)
        if parent1 == parent2: return False
        elif self.parent[parent1] <= self.parent[parent2]: self.parent[parent1] += self.parent[parent2]; self.parent[parent2] = parent1
        else: self.parent[parent2] += self.parent[parent1]; self.parent[parent1] = parent2
        return True
    def getCount(self, node):  return -self.parent[self.getParent(node, node)] # O(log(n))

from math import floor
def solve(p, q):
    if p < q: return p
    if p % q: return p
    factors = set()
    for i in range(2, floor(q ** 0.5) + 1):
        if q % i == 0:
            factors.add(i)
            factors.add(q//i)
    factors.add(q)
    factors = list(factors)
    # print(factors)
    if factors == []: return 1
    if p == q:
        return p // min(factors)

    count = []
    for i in factors:
        q1 = q
        cnt = 0
        while q1 % i == 0:
            q1 = q1//i
            cnt += 1
        count.append(cnt)
    # print(count)


    count1 = []
    for i in factors:
        p1 = p
        cnt = 0
        while p1 % i == 0:
            p1 = p1//i
            cnt += 1
        count1.append(cnt)
    # print(count1)

    ans = float("-inf")
    for i in range(len(factors)):
        p1 = p
        for j in range(count1[i] - count[i] + 1):
            p1 = p1//factors[i]
            if p1 % factors[i]:
                break

        ans = max(ans, p1)
    if ans == float("-inf"):
        return 1
    return ans

for _ in range(int(input())): # Multicase
    p, q = list(map(int, input().split()))
    print(solve(p, q))