팩토리얼과 거듭제곱

수학 나라에 전쟁이 일어났다. 팩토리얼 진영과 거듭제곱 진영은 누가 수학 나라를 지배할 것인지 결정하기 위해 싸우고 있다.

팩토리얼 진영의 유명한 장군 n은 자기 자신을 팩토리얼 계산을 하면서 훈련을 하고 있고, 거듭제곱진영의 제독 k는 자기 자신에 i제곱을 하기 위해 i를 만들고 있었다.

드디어 오늘은 n과 k가 싸우는 날이다. k는 n을 나누어서 작은 수로 만들어 버리기 위해서 몇 년동안 훈련을 진행하고 있었다.

이제 k는 n을 나누려고 한다. 훈련을 통해서 모두 성장했으므로, n!와 ki와 싸우는 것이다.

이때, n!을 ki로 나눌 수 있는 가장 큰 i를 찾는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100) 다음 T개의 줄에는 n과 k가 공백으로 구분되어 주어진다. (2 ≤ n ≤ 1018, 2 ≤  k ≤ 1012)

각각의 테스트 케이스에 대해서, 가장 큰 i를 한 줄에 하나씩 출력한다.