#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000000


using namespace std;

ll t,n,k;

ll fac(ll n){
	
	if(n==0){
		return 1;
	}

	return n * fac(n-1);
}

int main(){
	cin >> t;
	while(t--){
		cin >> n >>k;
		
		ll a = fac(n);
		ll b = 1;
		ll x = 0;

		while(a%b == 0){
			b = b*k;
			x++;
		}

		cout << x-1 << endl;

	}
	return 0;

}