for _ in range(int(input())):
    
    N, K = map(int, input().split())
    
    x = 1
    j = 0
    if K == 1:
        print(N - 1)
        continue
    while N > x:
        x *= K
        x += 1
        j += 1
        
    print(j)