팩토리얼과 거듭제곱

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

팩토리얼 진영의 이름난 장군 $n$ 은 자기 자신의 팩토리얼을 계산하며 훈련하여 $n!$ 만큼 강해졌고, 거듭제곱 진영의 제독 $k$ 는 자기 자신을 $i$ 제곱 하기 위한 지수 $i$ 를 준비하며 $k^i$ 만큼 강해졌다.

드디어 오늘, $n$ 과 $k$ 가 맞붙는 날이 왔다. 제독 $k$ 는 장군 $n$ 을 나누어 더 작은 수로 만들어 버리려고 몇 년 동안 훈련해 왔다.

둘 다 훈련으로 성장했으므로 실제로는 $n!$ 과 $k^i$ 가 싸우는 셈이다. 이때 $n!$ 이 $k^i$ 으로 나누어떨어지게 하는 가장 큰 $i$ 를 찾는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. ($1 \le T \le 100$)

다음 $T$ 개의 줄에는 각각 두 정수 $n$ 과 $k$ 가 공백으로 구분되어 주어진다. ($2 \le n \le 10^{18}$, $2 \le k \le 10^{12}$)

각 테스트 케이스마다 조건을 만족하는 가장 큰 $i$ 를 한 줄에 하나씩 출력한다.