q = int(input())
for i in range(0, q):
    n, k = map(int, input().split())
    if k == 1:
        print(n-1)
    else:
        res = 0
        key = 1
        while key < n:
            res += 1
            key += k**res
        print(res)