q = int(input())
for _ in range(q):
    n, k = map(int, input().split())
    ans = 0
    a = 1
    i = 1
    while a < n:
        a += k**i
        i += 1
    print(i - 1)