← 返回题目列表

Codeforces · 1814/B

B. 长腿

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

机器人被放置在无限网格的 $$$(0, 0)$$$ 单元格中。该机器人具有可调节长度的腿。最初,它的腿长度为 $$$1$$$。

让机器人当前位于单元格 $$$(x, y)$$$ 中,并且腿长度为 $$$m$$$。一次移动,它可以执行以下三个操作之一:

- 跳转到单元格$$$(x + m, y)$$$;
- 跳转到单元格$$$(x, y + m)$$$;
- 将腿的长度增加$$$1$$$,i。 e.将其设置为 $$$m + 1$$$。

机器人到达单元格 $$$(a, b)$$$ 所需移动的最少次数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的唯一行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le 10^9$$$) - 结束单元格。

输出

对于每个测试用例,打印一个整数 - 机器人从单元格 $$$(0, 0)$$$ 到达单元格 $$$(a, b)$$$ 所需的最小移动次数。

示例

输入 #1

3
1 1
1 6
8 4

输出 #1

2
5
6

注意

在第一个测试用例中,机器人可以首先跳到 $$$(0, 1)$$$,然后跳到 $$$(1, 1)$$$。如果它增加腿的长度,它只能跳过 $$$(1, 1)$$$。

在第二个测试用例中,机器人可以跳转到$$$(1, 0)$$$,然后将其长度增加到$$$2$$$并跳转3次以到达$$$(1, 6)$$$。

在第三个测试用例中,机器人可以将腿的长度增加三倍,使其达到 $$$4$$$。然后跳转到$$$(0, 4)$$$。然后跳两次到达 $$$(8, 4)$$$。