c=int(input())
for _ in [0]*c:
	t,m=-1,0
	n,k=map(int,input().split())
	while n>m: t+=1; m+=k**t
	print(t)