import math

q = int(input())

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