You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 非常喜欢数学，小 Y 准备考考小 Z 的数学能力。

小 Y 会跟小 Z 提出 $t$ 个问题，每个问题都会给出两个整数 $p$ 和 $q$，问满足 $x \mid p$ 但 $q \nmid x$ 的最大的整数 $x$ 是多少？

提示：

1. $a \mid b$ 表示 $a$ 整除 $b$，即 $a$ 是 $b$ 的因数，$b$ 是 $a$ 的倍数；$a \nmid b$ 表示 $a$ 不能整除 $b$，表示 $a$ 不是 $b$ 的因数

2. 题意可以描述成，找到一个最大的 $x$，使得 $x$ 是 $p$ 的因数，但 $x$ 不是 $q$ 的倍数。

输入格式

第一行输入一个整数 $t$ 表示询问次数。

接下来 $t$ 行，每行输入两个整数 $p$ 和 $q$。

输出格式

输出共 $t$ 行，一行一个整数表示答案。

样例 #1

样例输入 #1

3
10 4
12 6
179 822

样例输出 #1

10
4
179

提示

【样例解释】

• 第一次询问，$10$ 本身就不是 $4$ 的倍数，所以输出 $10$；

• 第二次询问，$12$ 的因数有 $1,2,3,4,6,12$，其中 $4$ 是最大的不是 $6$ 的倍数的数。

【数据范围】

对于 $30\%$ 的数据，$1\le t \le 10, 1 \le p \le 10^7, 2 \le q \le 10^4$。

对于 $60\%$ 的数据，$1\le t \le 30, 1 \le p \le 10^{12}, 2 \le q \le 10^6$。

对于 $100\%$ 的数据，$1\le t \le 50, 1 \le p \le 10^{18}, 2 \le q \le 10^9$。