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