The Knight's Journey

Time limit1sMemory limit128 MB

Summary

For each target square (x, y) up to 1e9 away, find the smallest number of knight moves needed to reach it from the origin.

Level: Medium7 of 10
Topics: Math, Greedy, Brute force, Implementation
Solved: No attempts yet

Problem

In chess, a knight moves two squares in one direction and one square perpendicular to it: two squares horizontally and one vertically, or one square horizontally and two vertically. On an infinitely large chessboard, a knight standing at $(0, 0)$ can therefore move in a single step to any of $(1, 2)$ , $(-1, 2)$ , $(1, -2)$ , $(-1, -2)$ , $(2, 1)$ , $(-2, 1)$ , $(2, -1)$ , $(-2, -1)$ .

Given two integers $x$ and $y$ , write a program that computes the minimum number of moves a knight needs to travel from $(0, 0)$ to $(x, y)$ on this infinite board.

Input

The input consists of several test cases. Each test case is a single line containing two integers $x$ and $y$ separated by a space. The absolute value of each does not exceed one billion ( $10^9$ ).

The last line of the input contains END, which marks the end of the input.

Output

For each test case, output on its own line the minimum number of moves the knight needs to go from $(0, 0)$ to $(x, y)$ .

Examples1

Example 1
Input
```
1 2
2 4
END
```
Expected output
```
1
2
```