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 math 
import os
import sys
from io import BytesIO, IOBase

def fact (n):

    ans = dict() 
    while (n%2 == 0):
        ans[2] = ans.get(2, 0) + 1 
        n = n//2 
    
    for i in range (3, int(math.sqrt(n))+1, 2): 
        while (n%i == 0): 
            ans[i] = ans.get(i, 0) + 1 
            n = n//i 
    
    if (n > 2) :
        ans[n] = ans.get(n, 0) + 1 
    
    return ans

def count (n, p):

    count = 0 
    while (n%p == 0) :
        count += 1 
        n = n//p 
    return count 

def main():
    t = int(input()) 
    for _ in range (t):
        p,q = map(int, input().split()) 
        
        if (p < q): 
            print (p) 
        
        elif (p > q) : 
            if (p%q != 0): 
                print (p) 
            else: 
                Q = fact(q) 
                toDivide = list() 

                for f in Q.keys(): 
                    p1 = count (p, f)  
                    q1 = Q[f] 
                    toDivide.append (pow(f, p1-q1+1)) 
                
                print(p//min(toDivide)) 
        else:
            P = fact(p) 
            factors = list(P.keys()) 
            print(p//min(factors))  

# region fastio
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 = lambda s: self.buffer.write(s.encode()) if self.writable else None

    def read(self):
        if self.buffer.tell():
            return self.buffer.read().decode("ascii")
        return os.read(self._fd, os.fstat(self._fd).st_size).decode("ascii")

    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().decode("ascii")

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


def print(*args, sep=" ", end="\n", file=sys.stdout, flush=False):
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(end)
    if flush:
        file.flush()

sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion
sys.setrecursionlimit(10000)
if __name__ == "__main__":
    main()