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