Q = int(input())
for _ in range(Q):
    N, K = map(int, input().split())
    if K == 1:
        print(N-1)
    else:
        ans = 0
        a = 1
        s = 1
        while s < N:
            a *= K
            s += a
            ans += 1
        print(ans)