CF1444A.Division

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?

奥列格最喜欢的科目是历史和数学，而他最钟爱的数学分支是除法。

为了提升自己的除法能力，奥列格构造了 $t$ 对整数 $p_i$ 和 $q_i$，并对每一对数，他希望找出满足以下条件的最大整数 $x_i$：

• $p_i$ 能被 $x_i$ 整除；
• $x_i$ 不能被 $q_i$ 整除。

奥列格的除法能力非常出色，很快就求出了所有答案。你呢？

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.

第一行包含一个整数 $t$（$1 \le t \le 50$）—— 表示数对的个数。

接下来的 $t$ 行，每行包含两个整数 $p_i$ 和 $q_i$（$1 \le p_i \le 10^{18}$；$2 \le q_i \le 10^{9}$）—— 表示第 $i$ 个数对。

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.

输出 $t$ 个整数：第 $i$ 个整数是满足以下条件的最大 $x_i$：$p_i$ 能被 $x_i$ 整除，但 $x_i$ 不能被 $q_i$ 整除。

可以证明，在给定约束条件下，总存在至少一个满足整除条件的 $x_i$ 值。

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

对于第一组数，其中 $p_1 = 10$ 且 $q_1 = 4$，答案为 $x_1 = 10$，因为它是 $10$ 的最大因数，且 $10$ 不能被 $4$ 整除。

对于第二组数，其中 $p_2 = 12$ 且 $q_2 = 6$，注意到：

• $12$ 不是合法的 $x_2$，因为 $12$ 能被 $q_2 = 6$ 整除；
• $6$ 同样不是合法的 $x_2$：$6$ 也能被 $q_2 = 6$ 整除。

$p_2 = 12$ 的下一个可用因数是 $4$，即为答案，因为 $4$ 不能被 $6$ 整除。