Q = int(input())

for _ in range(Q):
    N, K = map(int, input().split())
    
    if K == 1:
        print(N - 1)
        continue
    
    s = 0
    i = 0
    
    while True:
        s += K ** i
        
        if s >= N:
            print(i)
            break
        
        i += 1