Q = int(input())
for _ in range(Q):
	T, M = -1, 0
	N, K = map(int,input().split())
	if K == 1: print(N - 1)
	else: 
		while N > M: T += 1; M += K ** T	
		print(T)