q = int(input())
for i in range(q):
    n, k = map(int, input().split())
    if k == 1:
        print(n-1)
        continue
    for d in range(10**9):
        if (k**d-1)//(k-1) >= n:
            print(d-1)
            break