您有两个正整数 $$$a$$$ 和 $$$b$$$。
您可以执行两种操作:
- $$$a = \lfloor \frac{a}{b} \rfloor$$$ (将 $$$a$$$ 替换为 $$$a$$$ 和 $$$b$$$ 之间除法的整数部分)
- $$$b=b+1$$$($$$b$$$ 增加 $$$1$$$)
求使 $$$a=0$$$ 所需的最少操作数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的描述中唯一一行包含两个整数$$$a$$$, $$$b$$$ ($$$1 \le a,b \le 10^9$$$)。
输出
对于每个测试用例,打印一个整数:使 $$$a=0$$$ 所需的最少操作数。
示例
输入 #1
6 9 2 1337 1 1 1 50000000 4 991026972 997 1234 5678
输出 #1
4 9 2 12 3 1
注意
在第一个测试用例中,最佳解决方案之一是:
1. 将 $$$a$$$ 除以 $$$b$$$。执行此操作后,$$$a = 4$$$ 且 $$$b = 2$$$。
2. 将 $$$a$$$ 除以 $$$b$$$。执行此操作后,$$$a = 2$$$ 且 $$$b = 2$$$。
3. 增加$$$b$$$。执行此操作后,$$$a = 2$$$ 且 $$$b = 3$$$。
4. 将 $$$a$$$ 除以 $$$b$$$。执行此操作后,$$$a = 0$$$ 且 $$$b = 3$$$。