Division

Description:

Input:

The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of pairs.

Each of the following $$$t$$$ lines contains two integers $$$p_i$$$ and $$$q_i$$$ ($$$1 \le p_i \le 10^{18}$$$; $$$2 \le q_i \le 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.

Sample Input:

3
10 4
12 6
179 822

Sample 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$$$.