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.
# Author : shadoX #
import sys
input=sys.stdin.buffer.readline
ri=lambda: int(input())
rl=lambda: list(map(int,input().split()))
rs=lambda: input().decode().rstrip('\n\r')
wrt=sys.stdout.write
pr=lambda *args,end='\n': wrt(' '.join([str(x) for x in args])+end)
xrange=lambda args: reversed(range(args))
cdiv=lambda x,y: (-(-x//y))
enum=enumerate; inf=float('inf')
mod=10**9 + 7
# Am I debugging ? Check if I'm using same variable name in two places
# fun() returning empty list ? check new=temp[:] or new=temp

from collections import Counter


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def memodict(f):
    """memoization decorator for a function taking a single argument"""
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret

    return memodict().__getitem__


def pollard_rho(n):
    """returns a random factor of n"""
    if n & 1 == 0:
        return 2
    if n % 3 == 0:
        return 3

    s = ((n - 1) & (1 - n)).bit_length() - 1
    d = n >> s
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        p = pow(a, d, n)
        if p == 1 or p == n - 1 or a % n == 0:
            continue
        for _ in range(s):
            prev = p
            p = (p * p) % n
            if p == 1:
                return gcd(prev - 1, n)
            if p == n - 1:
                break
        else:
            for i in range(2, n):
                x, y = i, (i * i + 1) % n
                f = gcd(abs(x - y), n)
                while f == 1:
                    x, y = (x * x + 1) % n, (y * y + 1) % n
                    y = (y * y + 1) % n
                    f = gcd(abs(x - y), n)
                if f != n:
                    return f
    return n


@memodict
def prime_factors(n):
    """returns a Counter of the prime factorization of n"""
    if n <= 1:
        return Counter()
    f = pollard_rho(n)
    return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def do(p,q,x):
	cnt=0
	while(q%x==0):
		cnt+=1
		q//=x 
	while(p%x==0):
		p//=x
	for i in range(cnt-1):
		p*=x 
	return p


from math import gcd
Cases=ri()
for Case in range(Cases):
	p,q=rl()
	#print('dfghdhg',p%q)
	if p%q:
		print(p)
	else:
		ans=1
		for x in prime_factors(q):
			ans=max(ans,do(p,q,x))
		print(ans)

		
		