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 itertools


def prime_sieve(limit):
    prime = [True] * limit
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        if is_prime:
            yield i
            for n in range(i * i, limit, i):
                prime[n] = False


primes = list(prime_sieve(10 ** 6))


def factors(n):
    global primes
    prod = 1
    fs = []
    for p in primes:
        if p * prod > n:
            break
        n_ = n
        i = 0
        while n_ % p == 0:
            i += 1
            prod *= p
            n_ = n_ // p
        if i > 0:
            fs.append((p, i))
    if len(fs) == 0:
        fs.append((n, 1))
    # assert n == math.prod([p ** i for (p, i) in fs]), (n, fs)
    # reduce(operator.mul, [p ** i for (p, i) in fs], 1), (n, fs)
    return fs


def combinations(xs):
    ss = []
    for (a, n) in xs:
        ys = []
        for i in range(n + 1):
            ys.append((a, i))
        ss.append(ys)
    return itertools.product(*ss)


def divisors(n):
    fs = factors(n)
    ds = []
    for c in combinations(fs):
        v = 1
        for (a, i) in c:
            v *= a ** i
        ds.append(v)
    return sorted(ds)


def main():
    n = int(input())
    for _ in range(n):
        p, q = tuple(map(int, input().split()))
        print(f(p, q))


def f(p, q):
    if p % q != 0:
        return p
    ds = factors(q)
    cand = []
    for (d, i) in ds:
        p_ = p
        d_ = d#**i
        while p_ % q == 0:
            if p_ % d_ == 0:
                p_ = p_ // d_
            else:
                break
        cand.append(p_)
    return max(cand)


main()
