q = int(input())
nk = [list(map(int, input().split())) for _ in range(q)]

for n, k in nk:
    n -= 1
    if k == 1:
        d = n
    else:
        d = 0
        c = k
        while n > 0:
            n -= c
            d += 1
            c *= k

    print(d)