Long Legs
Contest: Educational Codeforces Round 146 (Rated for Div. 2)
Difficulty rating: 1700
Tags: brute force, math

A robot is placed in a cell $$$(0, 0)$$$ of an infinite grid. This robot has adjustable length legs. Initially, its legs have length $$$1$$$.

Let the robot currently be in the cell $$$(x, y)$$$ and have legs of length $$$m$$$. In one move, it can perform one of the following three actions:

- jump into the cell $$$(x + m, y)$$$;
- jump into the cell $$$(x, y + m)$$$;
- increase the length of the legs by $$$1$$$, i. e. set it to $$$m + 1$$$.

What's the smallest number of moves robot has to make to reach a cell $$$(a, b)$$$?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$) — the ending cell.

Output format:
For each test case, print a single integer — the smallest number of moves the robot is required to make to reach a cell $$$(a, b)$$$ from a cell $$$(0, 0)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, the robot can first jump to $$$(0, 1)$$$, then to $$$(1, 1)$$$. If it ever increases the length of its legs, it will only be able to jump past $$$(1, 1)$$$.

In the second testcase, the robot can jump to $$$(1, 0)$$$, then increase the length of its length to $$$2$$$ and jump three times to reach $$$(1, 6)$$$.

In the third testcase, the robot can increase the length of its legs three times to make it $$$4$$$. Then jump to $$$(0, 4)$$$. Then jump twice to reach $$$(8, 4)$$$.

Example input:
3
1 1
1 6
8 4

Example output:
2
5
6

Editorial:
Let's fix the number of leg length increases we do. Let the final length be $$$k$$$. Notice that for all $$$i$$$ from $$$1$$$ to $$$k$$$ there is some time when the length is exactly $$$i$$$. Thus, we can perform jumps of form $$$(x, y) \rightarrow (x + i, y)$$$ or $$$(x, y) \rightarrow (x, y + i)$$$.
What's the jumping strategy, then? Obviously, we can solve the problem independently for $$$a$$$ and $$$b$$$. Consider $$$a$$$. We would love to just make jumps of length $$$k$$$ as that's the maximum possible length. Unfortunately, that only works when $$$a$$$ is divisible by $$$k$$$. Otherwise, we are left with some remainder which is smaller than $$$k$$$. But we have already figured out how to jump to any value from $$$1$$$ to $$$k$$$. So, that only adds another jump. You can say that the total number of jumps is $$$\lceil \frac a k \rceil$$$.
Same for $$$b$$$. Finally, for a fixed $$$k$$$, the answer is $$$\lceil \frac a k \rceil + \lceil \frac b k \rceil + (k - 1)$$$.
The constraints tell us that we are not allowed to iterate over all $$$k$$$ from $$$1$$$ to $$$\max(a, b)$$$. It feels like huge $$$k$$$ will never be optimal, but let's try to base our intuition on something.
Try to limit the options by studying the formula. Let's simplify. Assume $$$a = b$$$ and also get rid of the ceil. Not like that changes the formula a lot. Now it becomes $$$2 \frac a k + (k - 1)$$$. We can see that when we increase $$$k$$$, $$$2 \frac a k$$$ becomes smaller and $$$(k - 1)$$$ becomes larger. However, we care more about how fast they become smaller and larger. You can just guess or write down the derivative explicitly and figure out that the first term shrinks faster than the second term grows until around $$$\sqrt a \cdot c$$$ for some constant $$$c$$$ (apparently, $$$c = \sqrt 2$$$). Thus, their sum decreases until then, then increases.
Thus, you can search for the best $$$k$$$ around $$$\sqrt a$$$ or $$$\sqrt b$$$ or $$$\sqrt{\max(a, b)}$$$. It doesn't really matter, since, for implementation, you can basically try all $$$k$$$ until around $$$10^5$$$, which is safely enough.