codeforces#P1814B. Long Legs
Long Legs
Description
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)$?
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.
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)$.
Input
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
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)$.
3
1 1
1 6
8 4
2
5
6
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)$.