Из предметов в школе Олегу больше всего нравятся история и математика, а его любимый раздел математики — деление.
Чтобы улучшить свои навыки в делении, Олег загадал \(t\) пар целых чисел \(p_i\) и \(q_i\) и решил для каждой пары найти максимальное число \(x_i\), такое что
- \(p_i\) делится нацело на \(x_i\),
- \(x_i\) не делится нацело на \(q_i\).
Так как Олег очень хорош в делении, то он быстро нашёл нужный числа. Теперь ему интересно, сможете ли вы тоже справиться с этой задачей.
Выходные данные
Выведите \(t\) целых чисел, где \(i\)-е число — это максимальное число \(x_i\), такое что \(p_i\) делится нацело на \(x_i\), а \(x_i\) не делится нацело на \(q_i\).
Можно показать, что при заданных ограничениях всегда существует хотя бы один подходящий \(x_i\).
Примечание
Для \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 4
12 6
179 822
|
10
4
179
|