q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    phase=0
    while a>=0:
        a-=b**phase
        if a<=0:
            break
        phase+=1
    print(phase)