q = int(input())
for i in range(q):
    n, k = map(int, input().split())
    if k == 1:
        print(n-1)
    else:
        ans = 0
        sum = 1
        cnt = 1
        while sum < n:
            ans += 1
            cnt *= k
            sum += cnt
        print(ans)