N = int(input())
for i in range(N) :
    a,b = map(int,input().split())
    c = 0
    while a > 0 :
        
        a -= b ** c
        c += 1
    print(c-1)