#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
int main() {
  int Q; cin >> Q;
  vector<pair<int,int>> NK(Q);
  for(int i = 0; i < Q; i++) {
    int a,b; cin >>a >> b;
    NK[i] = {a,b};
  }
  for(int i = 0; i < Q; i++) {
    int x = NK[i].first;
    int y = NK[i].second;
    
    if(y == 1) {
      cout << x- 1 << endl;
      continue;
    }
    int ans = 0;
    if(x % y == 0) ans -= 1;
    while(true) {
      if(x == 0) break;
      x /= y;
      ans++;
    }
    
    cout <<ans << endl;
  }
}