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
import math
input = sys.stdin.readline
def get_int():
    return int(input().strip())
def get_int_list():
    return list(map(int, input().strip().split()))
def get_char_list():
    return list(input().strip())

def get_prime_list(v):
    target = int(math.sqrt(v))
    prime = [1] * target
    prime[0] = 0
    for i in range(1, target):
        if prime[i]:
            for j in range(i + i + 1, target, i + 1):
                prime[j] = 0
    fp = []
    for i, v in enumerate(prime):
        if v:
            fp.append(i + 1)
    return fp

def get_factor(v, prime_list):
    factor = []
    p_index = 0
    while v != 1:
        if v % prime_list[p_index] == 0:
            count = 0
            while v % prime_list[p_index] == 0:
                count += 1
                v //= prime_list[p_index]
            factor.append((prime_list[p_index], count))
        p_index += 1
        if p_index >= len(prime_list) and v != 1:
            factor.append((v, 1))
            v = 1
    return factor

def combine(f1, f2):
    factor = []
    i1 = 0
    i2 = 0
    while i1 < len(f1) and i2 < len(f2):
        v1, c1 = f1[i1]
        v2, c2 = f2[i2]
        if v1 == v2:
            factor.append((v1, c1 + c2))
            i1 += 1
            i2 += 1
        elif v1 > v2:
            factor.append((v2, c2))
            i2 += 1
        else:
            factor.append((v1, c1))
            i1 += 1
    if i1 < len(f1):
        factor.extend(f1[i1:])
    if i2 < len(f2):
        factor.extend(f2[i2:])
    return factor


cases = get_int()
prime_list = get_prime_list(1e9)
for _ in range(cases):
    p, q = get_int_list()
    if p % q != 0:
        print(p)
    else:
        orig_p = p
        q_factor = get_factor(q, prime_list)
        p_factor = []
        while p % q == 0:
            p_factor = combine(p_factor, q_factor)
            p //= q
        p_factor = combine(p_factor, get_factor(p, prime_list))
        #print(p_factor, q_factor)
        p_i = 0
        q_i = 0
        minv = orig_p
        while p_i < len(p_factor) and q_i < len(q_factor):
            pv, pc = p_factor[p_i]
            qv, qc = q_factor[q_i]
            if pv == qv:
                tv = pow(pv, pc - (qc - 1))
                #print(tv)
                minv = min(tv, minv)
                p_i += 1
                q_i += 1
            elif pv > qv:
                q_i += 1
            else:
                p_i += 1
        print(orig_p // minv)