import java.util.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int q = sc.nextInt(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { sb.append(getCount(sc.nextInt(), sc.nextInt())).append("\n"); } System.out.print(sb); } static int getCount(long n, int k) { int idx = 0; while (n > 0) { n -= (long)(Math.pow(k, idx)); idx++; } return idx - 1; } }