29043번 - Мэйвис и Дракула 다국어

문제

Сегодня один из тех вечеров, когда Мэйвис и Дракула проводят время вместе. Дракула решил поиграть с дочкой в игру. Она, конечно же, как вы уже наверное догадались, имеет математическую основу.

Состоит эта игра в следующем: Дракула говорит Мэйвис натуральные числа $A$ и $B,ドル после чего Мэйвис должна найти такое натуральное число $x,ドル не превосходящее $B,ドル что $lcm(A, x)$ максимально среди всех натуральных чисел, не превосходящих $B$. Дракула хочет сыграть с дочкой $T$ раундов.

Мэйвис достаточно быстро поднадоела эта математическая игра, и она решила попросить вас написать программу, которая по заданным $A$ и $B$ будет находить число наибольшее значение $lcm,ドル которого можно достигнуть.

입력

В первой строке содержится одно натуральное число $T$ (1ドル \le T \le 10^5$) --- количество раундов в игре. В следующих $T$ строках содержатся числа $A$ и $B$ (1ドル \le A, B \le 3 \times{} 10^9$) для каждого раунда.

출력

В $T$ строках должны содержаться ответы для раундов --- наибольшее значение $lcm,ドル которого можно достигнуть в этом раунде.

제한

힌트