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