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

#define int long long
signed main(){
  int Q;
  cin>>Q;
  for(int i=0;i<Q;i++){
    int n,k;
    cin>>n>>k;
    if(k==1){
      cout<<n-1<<endl;
      continue;
    }
    int cnt=0;
    int temp=k;
    while(n>0){
      //cout<<"#"<<n<<" "<<temp<<endl;
      n-=temp;
      temp*=k;
      cnt++;
    }
    cout<<cnt<<endl;
  }
  return 0;
}