Q = int(input())
NK = [map(int,input().split()) for _ in range(Q)]

for N,K in NK:
  if K == 1:
    print(N-1)
  else:
    count = 0
    num = 0
    while num < N:
      num += K**(count+1)
      count += 1
    print(count)