eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Приклад

Вхідні дані #1
2
5 2
10 10
Вихідні дані #1
3
2
Джерело 2011 ICPC German Collegiate Programming Contest, Задача A