Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

math

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Long Legs

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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

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)$$$.

Example

Input

31 11 68 4

Output

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)$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 21:49:11 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|