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())
n_list = []
k_list = []
for i in range(q):
    n, k = map(int,input().split())
    n_list.append(n)
    k_list.append(k)
    
for i in range(q):
    query_calc(n_list[i], k_list[i])