#include <iostream>
using namespace std;

int main(){
  int Q;
  cin >> Q;
  while(Q--){
    int N, K;
    cin >> N >> K;
    int t = 1, ans = -1;
    while(N > 0) N -= t, t *= K, ++ans;
    cout << ans << endl;
  }
}