q = int(input()) info = [list(map(int, input().split())) for i in range(q)] for i in range(q): n, k = info[i] ans = 0 while n > 0: n -= k**ans ans += 1 print(ans - 1)