Задачи
Факульти делит степени
Факульти делит степени
Фред Факульти и Пол Пауэр любят большие числа. День за днём Фред выбирает случайное целое число $n$ и вычисляет $n!$. Его друг Пол развлекается, вычисляя несколько степеней случайно выбранного целого числа $k$, например $k^2$, $k^3$ и так далее. В жаркий летний день Фреду и Полу стало очень скучно, поэтому они решили подшутить над своим приятелем Дэйвом Дивайдером. Фред выбирает случайное целое число $n$, а Пол выбирает случайное целое число $k$. Они хотят, чтобы Дэйв нашел наибольшее целое число $i$, такое, что $k^i$ делит $n!$ без остатка, иначе они бросят Дэйву тортом в лицо.
Поскольку Дэйв не любит когда ему бросают пирожные в лицо, он хочет, чтобы Вы помогли ему найти такое целое число $i$.
\InputFile
Первая строка содержит количество тестов $t~(1 \le t \le 100)$. Каждая из следующих $t$ строк содержит два числа $n$ и $k~(2 \le n \le 10^{18}, 2 \le k \le 10^{12})$.
\OutputFile
Для каждого теста выведите максимальное целое число $i$ в отдельной строке.
Входные данные #1
2 5 2 10 10
Выходные данные #1
3 2