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.
import sys

sys.setrecursionlimit(10**5)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.buffer.readline())
def MI(): return map(int, sys.stdin.buffer.readline().split())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def BI(): return sys.stdin.buffer.readline().rstrip()
def SI(): return sys.stdin.buffer.readline().rstrip().decode()

def PrimeFactorization(x):
    def plist(x):
        if x < 2: return []
        if x & 1 == 0: return [2] + plist(x >> 1)
        for p in range(3, x + 1, 2):
            if x % p == 0: return [p] + plist(x // p)
            if p ** 2 > x: return [x]

    pl = plist(x)
    pp, ee = [], []
    for p in pl:
        if not pp or p != pp[-1]:
            pp += [p]
            ee += [0]
        ee[-1] += 1
    return [(p, e) for p, e in zip(pp, ee)]

def solve():
    if p%q:return p
    be=PrimeFactorization(q)
    mn=p
    for b,e in be:
        c=p
        c//=b**e
        cur=b
        while c%b==0:
            cur*=b
            c//=b
        mn=min(mn,cur)

    return p//mn

for _ in range(II()):
    p,q=MI()
    print(solve())
