from bisect import bisect_left

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