A. Деление
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Из предметов в школе Олегу больше всего нравятся история и математика, а его любимый раздел математики — деление.

Чтобы улучшить свои навыки в делении, Олег загадал $$$t$$$ пар целых чисел $$$p_i$$$ и $$$q_i$$$ и решил для каждой пары найти максимальное число $$$x_i$$$, такое что

  • $$$p_i$$$ делится нацело на $$$x_i$$$,
  • $$$x_i$$$ не делится нацело на $$$q_i$$$.
Так как Олег очень хорош в делении, то он быстро нашёл нужный числа. Теперь ему интересно, сможете ли вы тоже справиться с этой задачей.
Входные данные

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество пар чисел.

В следующих $$$t$$$ строках задано по два целых числа $$$p_i$$$ и $$$q_i$$$ ($$$1 \le p_i \le 10^{18}$$$; $$$2 \le q_i \le 10^{9}$$$) — $$$i$$$-я пара загаданых чисел.

Выходные данные

Выведите $$$t$$$ целых чисел, где $$$i$$$-е число — это максимальное число $$$x_i$$$, такое что $$$p_i$$$ делится нацело на $$$x_i$$$, а $$$x_i$$$ не делится нацело на $$$q_i$$$.

Можно показать, что при заданных ограничениях всегда существует хотя бы один подходящий $$$x_i$$$.

Пример
Входные данные
3
10 4
12 6
179 822
Выходные данные
10
4
179
Примечание

Для $$$p_1 = 10$$$, $$$q_1 = 4$$$ число $$$x_1 = 10$$$ подходит, так как это максимальный делитель $$$10$$$, и $$$10$$$ не делится на $$$4$$$.

Для $$$p_2 = 12$$$, $$$q_2 = 6$$$ заметим, что:

  • $$$12$$$ не подходит в качестве $$$x_2$$$, так как $$$12$$$ делится на $$$q_2 = 6$$$,
  • $$$6$$$ не подходит в качестве $$$x_2$$$, так как $$$6$$$ делится на $$$q_2 = 6$$$.
Следующий по величине делитель $$$p_2 = 12$$$ — это $$$4$$$, и он нам подходит, так как $$$4$$$ не делится нацело на $$$6$$$.