q=int(input())
for i in range(q):
  n,k=map(int,input().split())
  if k==1:
    print(n-1)
  else:
    v=1
    d=0
    while v<n:
      v+=k**d
      d+=1
    print(d if v==n else d-1)