Description:
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$$$.
Input Format:
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 Format:
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.
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$$$.