CF1444A Division

Oleg 最喜欢的科目是历史和数学，他最喜欢的数学分支是除法。

为了提升自己的除法能力，Oleg 想出了 t 对整数 p_i 和 q_i，并且对于每一对，他决定找到最大的整数 x_i，使得：

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

Oleg 非常擅长除法，很快就找到了所有答案，你能做到吗？

第一行包含一个整数 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 对整数。

输出 t 个整数，第 i 个整数表示最大的 x_i，满足 p_i 能被 x_i 整除，且 x_i 不能被 q_i 整除。

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

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

对于第二对数，p_2 = 12，q_2 = 6，注意：

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

12 的下一个约数是 4，它不能被 6 整除，因此答案是 4。