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
import math
import sys
import os
from collections import defaultdict

 
def is_debug():
    return "PYPY3_HOME" not in os.environ

def stdin_wrapper():
    data = '''10
246857872446986130 713202678
857754240051582063 933416507
873935277189052612 530795521
557307185726829409 746530097
173788420792057536 769449696
101626841876448103 132345797
598448092106640578 746411314
733629261048200000 361714100
981271355542147402 38
559754147245184151 431517529
'''
    
    for line in data.split('\n'):
        yield line
 
if not is_debug():
    def stdin_wrapper():
        while True:
            yield sys.stdin.readline()
 
inputs = stdin_wrapper()
 
def input_wrapper():
    return next(inputs)
 


def get_str():
    if is_debug():
        return input_wrapper()

    return input()

def get(_type):
    if _type == str:
        return get_str()

    return _type(input_wrapper())
 
def get_arr(_type):
    return [_type(x) for x in input_wrapper().split()]
 

def tuplerize(method):
    def wrap(*args, **kwargs):
        res = method(*args, **kwargs)
        if not isinstance(res, (tuple, list)):
            res = (res, )

        return res
    return wrap

''' Solution '''

@tuplerize
def solve(p, q):
    if p % q:
        return p

    l = []
    i = 2
    while i*i <= q:
        if not q % i:
            l.append(i)
            if i != q//i:
                l.append(q//i)
        i += 1

    l.append(q)
    res = 1
    for d in l:
        el = p
        while not el % d:
            el //= d
            if el % q:
                res = max(res, el)
                break

    return res



t = get(int)
for _ in range(t):
    a, b = get_arr(int)
    print(*solve(a,b))

