← 返回题目列表

Codeforces · 1444/A

A. 司

中文机器翻译题面 查看原题

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

为了提高他的除法技能,Oleg 提出了 $$$t$$$ 整数对 $$$p_i$$$ 和 $$$q_i$$$,并决定为每一对找到最大整数 $$$x_i$$$,这样:

- $$$p_i$$$ 可以被 $$$x_i$$$ 整除;
- $$$x_i$$$ 不能被 $$$q_i$$$ 整除。

输入

第一行包含一个整数 $$$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$$$ 始终至少有一个值满足给定约束的整除条件。

示例

输入 #1

3
10 4
12 6
179 822

输出 #1

10
4
179

注意

对于第一对,$$$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$$$ 整除。