#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int q; cin>>q;
	for(int i=0;i<q;++i){
		int64_t n,k; cin>>n>>k;
		int ans=0;
		if(k==1)ans=n-1;
		else for(int64_t j=1;j<n;j*=k)++ans;
		cout<<ans<<"\n"s;
	}
}