q = int(input())

nkq = [None] * q
for i in range(q):
    nkq[i] = list(map(int, input().split(' ')))

for nk in nkq:
    depth = 0
    c = nk[0]
    while(True):
        c -= pow(nk[1], depth)
        if c <= 0:
            break
        depth += 1
    print(depth)