Q = int(input())
ans = []
for i in range(Q):
    N,K = map(int,input().split())
    if K == 1:
        ans.append(N-1)
        continue
    d = 0
    while  (K**(d+1)-1)//(K-1) < N:
        d += 1
    ans.append(d)
print(*ans,sep='\n')