Факультети розподіляють ступені#6543
Фред Факульті та Пол Павер захоплюються великими числами. Щодня Фред обирає випадкове ціле число і обчислює . Його друг Пол розважається, обчислюючи різні степені випадково обраного цілого числа , такі як k^2, k^3 і так далі. Одного спекотного літнього дня Фред і Пол вирішили пожартувати над своїм приятелем Дейвом Дівайдером. Фред обирає випадкове ціле число , а Пол обирає випадкове ціле число . Вони хочуть, щоб Дейв знайшов найбільше ціле число , таке, що k^i ділить без залишку, інакше вони кинуть Дейву торт в обличчя.
Оскільки Дейв не любить, коли йому кидають тортами в обличчя, він просить вас допомогти йому знайти таке ціле число .
Перший рядок містить кількість тестів t~(1 \le t \le 100). Кожен з наступних рядків містить два числа і k~(2 \le n \le 10^{18}, 2 \le k \le 10^{12}).
Для кожного тесту виведіть максимальне ціле число в окремому рядку.
Приклад 1