Q = int(input())

def S(r, n):
    if r == 1:
        return n+1
    return (pow(r, n+1)-1)//(r-1)

for _ in range(Q):
    N,K = map(int, input().split())
    ans = 0
    while S(K, ans) < N:
        ans += 1
    print(ans)