Q = int(input())

for _ in range(Q):
    n, k = map(int,input().split())
    x = 1
    y = 1
    while x < n:
        x += k**y
        y += 1
    print(y - 1)