q = int(input())

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