#!/usr/bin/env python3
def f(n, k):
    if k == 1:
        return n - 1
    acc = 0
    d = -1
    while acc < n:
        d += 1
        acc += k ** d
    return d
q = int(input())
for _ in range(q):
    n, k = map(int, input().split())
    print(f(n, k))