Steps

Time limit1sMemory limit128 MB

Summary

Find the minimum number of steps from x to y when consecutive step lengths differ by at most 1 and the first and last lengths are 1.

Level: Medium5 of 10
Topics: Math, Greedy, Binary search
Solved: No attempts yet

Problem

You walk along the integer points of a straight line. Each step's length must be a nonnegative integer, and compared with the length of the immediately preceding step it must be larger by $1$ , equal, or smaller by $1$ .

What is the minimum number of steps needed to move from coordinate $x$ to coordinate $y$ ? The length of the first and the last step must be $1$ .

Input

The first line contains $n$ , the number of test cases. Each of the following test cases is a line with two integers $x$ and $y$ , satisfying $0 \le x \le y < 2^{31}$ .

Output

For each test case, print on its own line the minimum number of steps needed to move from $x$ to $y$ .

Examples1

Example 1
Input
```
3
45 48
45 49
45 50
```
Expected output
```
3
3
4
```