蒟蒻的尊严被打得一败涂地17
题目描述
小 Z 非常喜欢数学，小 Y 准备考考小 Z 的数学能力。
小 Y 会跟小 Z 提出 t 个问题，每个问题都会给出两个整数 p 和 q，问满足x∣p 但q∤x 的最大的整数 x 是多少？
提示：
- a∣b 表示 a 整除 b，即 a 是 b 的因数，b 是 a 的倍数；a∤b 表是a 不能整除 b，表示 a 不是 b 的因数
- 题意可以描述成，找到一个最大的 x，使得 x 是 p 的因数，但 x 不是q的倍数。
输入格式
第一行输入一个整数 t表示询问次数。
接下来 tt 行，每行输入两个整数 和 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≤t≤10,1≤p≤107,2≤q≤104
对于 60% 的数据，1≤t≤30,1≤p≤1012,2≤q≤106
对于 100%的数据，1≤t≤50,1≤p≤1018,2≤q≤109