A =int(input())
for i in range(A):
    n,k = map(int, input().split())
    p = 1
    a = 0
    if k == 1:
        a = n-1
    else:
        while p < n:
            p += k * k ** a
            a += 1
            
    print(a)