# No.897 compαctree q = int(input()) n = [] k = [] for i in range(q): tmp = [int(s) for s in input().split()] n.append(tmp[0]) k.append(tmp[1]) for i in range(q): if k[i] == 1: print(n[i] - 1) else: depth = 1 points = 1 while points < n[i]: points += k[i] ** depth depth += 1 print(depth - 1)