Q = int(input().strip())

def calc(N, K):
  N -= 1
  cnt = 0
  
  while N > 0:
    cnt += 1
    N -= K**cnt
  
  return cnt

for i in range(Q):
  N, K = map(int, input().strip().split(' '))
  
  ans = calc(N, K)
  print(ans)