def query_calc(n, k):
    nodes_per_stair = k ** 0
    ever_nodes = 1
    deep = 0

    while ever_nodes < n:
        deep += 1
        nodes_per_stair *= k
        ever_nodes += nodes_per_stair

    print(deep)

q = int(input())
for i in range(q):
    n, k = map(int,input().split())
    query_calc(n, k)