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