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$。 由 ChatGPT 4.1 翻译