Q = int(input())

def check(N,K):
    if K == 1:
        print(N-1)
        return
    ans = 0
    now = 1
    while now < N:
        now = now * K + 1
        ans += 1
    print(ans)
for _ in range(Q):
    N,K = list(map(int,input().split()))
    check(N,K)