题目描述

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

为了提高自己的除法技巧，奥列格想出了一个问题，问题是给你两个整数 $p_i$ 和 $q_i$ ，并决定为每对整数找出最大的整数 $x_i$ ，使得满足以下两个条件：

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

一共有 $t$ 组询问。

输入格式

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

输出格式

输出 $t$ 行，每行一个最大的整数 $x_i$ ，使得 $p_i$ 可以被 $x_i$ 整除，但是 $x_i$ 不能被 $q_i$ 整除。

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

3
10 4
12 6
179 822

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$ 整除。

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