Best Friends

Time limit1sMemory limit128 MB

Summary

Given two numbered circles in a triangular packing, compute the fewest adjacent moves between them.

Level: Medium5 of 10
Topics: BFS, Graph, Math
Solved: No attempts yet

Problem

Petey and Patty are best friends, and they are locked in a maze. The maze holds an infinite number of circles of the same size, packed into a triangle. The top row holds one circle, the second row holds two, and row $r$ holds $r$ circles. Two neighbouring rows sit half a circle apart, so a circle touches the circles beside it in its own row and the two circles under it in the next row. The circles are numbered row by row, from left to right.

         1
       2   3
     4   5   6
   7   8   9  10
11  12  13  14  15

Petey and Patty each stand on a circle, and the two circles are not necessarily different. In one step Petey moves from the circle she stands on to a circle adjacent to it. Two circles are adjacent when they share a point.

Given the numbers of the circles Petey and Patty stand on at the start, find the smallest number of steps Petey needs to reach her friend.

Input

The input holds several test cases. Each line holds two integers $a$ and $b$ , the number of the circle Petey stands on and the number of the circle Patty stands on. Neither number is more than $10000$ ( $1 \le a, b \le 10000$ ).

The last line is 0 0. It marks the end of the input and is not a test case.

Output

For the $i$ -th test case print one integer on the $i$ -th line of the output: the smallest number of steps Petey needs to reach her friend.

Examples2

Example 1
Input
```
1 3
2 6
23 9
0 0
```
Expected output
```
1
2
4
```
Example 2
Input
```
1 1
4 4
2 3
1 2
0 0
```
Expected output
```
0
0
1
1
```