from math import log

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