import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int q = sc.nextInt();
      while(q-- > 0) {
        int n = sc.nextInt();
        long k = sc.nextInt();
        if(k == 1) {
          System.out.println(n - 1);
          continue;
        }
        int d = 0;
        while(n > 0) {
          n -= Math.pow(k, d);
          if(n <= 0) break;
          d++;
        }
        System.out.println(d);
      }
  }
}