import math
Q=int(input())
for i in range(Q):
    N,K=map(int,input().split())
    if K==1:
        print(N-1)
    else:
        ans=math.floor(math.log(N*(K-1)+1,K))
        print(ans)