Факульти делит степени

Фред Факульти и Пол Пауэр любят большие числа. День за днём Фред выбирает случайное целое число $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$ в отдельной строке.

Примеры