import math

def deep_calc(n, k):
    res = None
    
    if k == 1:
        res = n - 1
    else:

        res = int(math.log(n * (k - 1) + 1, k))
        
    print(res)

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