← 返回题目列表

Codeforces · 1485/A

A. 加和除

中文机器翻译题面 查看原题

您有两个正整数 $$$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$$$。