#include <stdio.h>
#include <math.h>

int main() {
  int q;
  scanf("%d", &q);

  for (int i=0; i<q; i++) {
    int n, k, cnt=0;
    scanf("%d %d", &n, &k);

    if (k==1) {
      printf("%d\n", n-1);
    } else{
      for (long long j=1, l=1; j<=n; j+=pow(k, l), l++) {
        cnt++;
      }
      printf("%d\n", cnt);
    }
  }
  return 0;
}