Факультети розподіляють ступені

Фред Факульті та Пол Павер захоплюються великими числами. Щодня Фред обирає випадкове ціле число $n$ і обчислює $n!$. Його друг Пол розважається, обчислюючи різні степені випадково обраного цілого числа $k$, такі як $k^2$, $k^3$ і так далі. Одного спекотного літнього дня Фред і Пол вирішили пожартувати над своїм приятелем Дейвом Дівайдером. Фред обирає випадкове ціле число $n$, а Пол обирає випадкове ціле число $k$. Вони хочуть, щоб Дейв знайшов найбільше ціле число $i$, таке, що $k^i$ ділить $n!$ без залишку, інакше вони кинуть у Дейва тортом в обличчя.

Оскільки Дейв не любить, коли йому кидають тортами в обличчя, він просить вас допомогти йому знайти таке ціле число $i$.

Вхідні дані

Перший рядок містить кількість тестів $t(1\le t\le 100)$. Кожен з наступних $t$ рядків містить два числа $n$ і $k(2\le n\le 10^{18},2\le k\le 10^{12})$.

Вихідні дані

Для кожного тесту виведіть максимальне ціле число $i$ в окремому рядку.

Приклади