import sys
input = sys.stdin.readline

Q = int(input())
for _ in range(Q):
    N, K = map(int, input().split())
    if K == 1:
        print(N - 1)
        continue
    ans = -1
    for d in range(1000):
        if N <= (K ** (d + 1) - 1) // (K - 1):
            ans = d
            break
    print(ans)