Q = int(input())

for _ in range(Q):
    N, K = map(int, input().split())
    if K == 1:
        print(N-1)
        continue
    now = 1
    cnt = 1
    high = 0
    while cnt < N:
        now *= K
        cnt += now
        high += 1
    print(high)