#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	Q = int(input())
	for i in range(Q):
		N, K = getlist()
		if K == 1:
			print(N - 1)
		else:
			m = 1
			while True:
				if K ** m >= N * (K - 1) + 1:
					print(m - 1)
					break
				else:
					m += 1


if __name__ == '__main__':
	main()