小 Z 的整除问题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小 Z 非常喜欢数学,小 Y 准备考考小 Z 的数学能力。
小 Y 会跟小 Z 提出 个问题,每个问题都会给出两个整数 和 ,问满足 但 的最大的整数 是多少?
提示:
- 表示 整除 ,即 是 的因数, 是 的倍数; 表示 不能整除 ,表示 不是 的因数
- 题意可以描述成,找到一个最大的 ,使得 是 的因数,但 不是 的倍数。
输入格式
第一行输入一个整数 表示询问次数。
接下来 行,每行输入两个整数 和 。
输出格式
输出共 行,一行一个整数表示答案。
样例输入输出
3
10 4
12 6
179 822
10
4
179
提示
【样例解释】
- 第一次询问, 本身就不是 的倍数,所以输出 ;
- 第二次询问, 的因数有 ,其中 是最大的不是 的倍数的数。
【数据范围】
对于 的数据,。
对于 的数据,$1\le t \le 30, 1 \le p \le 10^{12}, 2 \le q \le 10^6$。
对于 的数据,$1\le t \le 50, 1 \le p \le 10^{18}, 2 \le q \le 10^9$。