Q=int(input())
for _ in range(Q):
	n,k=map(int,input().split())
	if k==1:
		print(n-1)
	else:
		c=0
		for i in range(100):
			c+=k**i
			if n<=c:
				print(i)
				break