Q = int(input())
for i in range(Q):
    tmp = 1
    i = 1
    N,K = map(int,input().split())
    while tmp < N:
        tmp += K**i
        i += 1
    print(i-1)