小 C 非常喜欢数学，小 A 准备考考小 C 的数学能力。

小 A 会向小 C 提出 t 个问题，每个问题都会给出两个整数 p 和 q ，问满足 x 能整除 p 且 x 不是 q 的倍数的 x 的最大值是多少？

第一行输入一个整数 t，表示提问 t 次 。 

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

样例解析： 

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

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

数据范围： 

对于 30% 的数据，1 ≤ t ≤ 10，1 ≤ p ≤ 10⁷，2 ≤ q ≤ 10⁴， 

对于 60% 的数据，1 ≤ t ≤ 30，1 ≤ p ≤ 10¹²，2 ≤ q ≤ 10⁶， 

对于 100% 的数据，1 ≤ t ≤ 50，1 ≤ p ≤ 10¹⁸，2 ≤ q ≤ 10⁹。