#yuki897

def num(x,y):
 i=0
 while y**i<=x:
  i+=1
 return i

q=int(raw_input())
for i in range(q):
 n,k=map(int,raw_input().split())
 if k==1:
  print n-1
 else:
  print num(n,k)