Фред Факульти и Пол Пауэр любят большие числа. День за днём Фред выбирает случайное целое число n и вычисляет n!. Его друг Пол развлекается, вычисляя несколько степеней случайно выбранного целого числа k, например k2, k3 и так далее. В жаркий летний день Фреду и Полу стало очень скучно, поэтому они решили подшутить над своим приятелем Дэйвом Дивайдером. Фред выбирает случайное целое число n, а Пол выбирает случайное целое число k. Они хотят, чтобы Дэйв нашел наибольшее целое число i, такое, что ki делит n! без остатка, иначе они бросят Дэйву тортом в лицо.
Поскольку Дэйв не любит когда ему бросают пирожные в лицо, он хочет, чтобы Вы помогли ему найти такое целое число i.
Первая строка содержит количество тестов t (1≤t≤100). Каждая из следующих t строк содержит два числа n и k (2≤n≤1018,2≤k≤1012).
Для каждого теста выведите максимальное целое число i в отдельной строке.