Из предметов в школе Олегу больше всего нравятся история и математика, а его любимый раздел математики — деление. Чтобы улучшить свои навыки в делении, Олег загадал два целых числа $$$p$$$ и $$$q$$$ и решил найти максимальное число $$$x$$$, такое что $$$p$$$ делится нацело на $$$x$$$, а $$$x$$$ не делится нацело на $$$q$$$. Так как Олег очень хорош в делении, то он быстро нашёл нужное число. Теперь ему интересно, сможете ли вы тоже справиться с этой задачей.
В первой строке задано целое число $$$p$$$ ($$$1 \le p \le 10^{100}$$$).
Во второй строке задано целое число $$$q$$$ ($$$2 \le q \le 10^{12}$$$).
Можно показать, что при данных ограничениях существует хотя бы одно подходящее $$$x$$$.
Выведите максимальное число $$$x$$$, такое что $$$p$$$ делится нацело на $$$x$$$, а $$$x$$$ не делится на $$$q$$$.
10 4
10
12 6
4
179 822
179
В первом примере число $$$x = 10$$$ подходит, так как это максимальный делитель $$$10$$$, и $$$10$$$ не делится на $$$4$$$.
Во втором примере заметим, что число $$$12$$$ не подходит в качестве $$$x$$$, так как $$$12$$$ делится на $$$6$$$, $$$6$$$ не подходит в качестве $$$x$$$, так как $$$6$$$ делится на $$$6$$$, а следующий по величине делитель $$$12$$$ — это $$$4$$$, и $$$x=4$$$ нам подходит, так как $$$4$$$ не делится нацело на $$$6$$$.
