007 - ハチの巣距離

時間制限 8 秒 / メモリ制限 256 MB / 得点 30 / x 10 /


TLE
8sec
MLE
256MB
得点
30

問題

正六角形が敷き詰められた平面がある.六角形の 1 つ 1 つをマスと呼び,あるマスから 1 ステップで,辺で接するマスへ移動できる.中央のマスから指定されたマスに移動するには,少なくとも何ステップ必要であるかを求めたい.

マスの指定のために,各マスを 2 つの整数の組で表す.中央のマスは (0, 0) である.マスの辺に垂直な向きの 1 つを右向きとし,各マス (x, y) について,右隣のマスが (x + 1, y),右上隣のマスが (x, y + 1) である(下図参照).

2 つの整数 x, y が与えられたとき,マス (0, 0) からマス (x, y) まで移動するために必要なステップ数の最小値を求めるプログラムを書きなさい.

図 1: マスの指定方法

Input

入力の 1 行目はデータセットの個数を表す正の整数 n のみからなり,n は 100 を超えない.続く n 行の各行に 1 つずつデータセットが与えられる.

各データセットは,2 つの整数 xy からなる.(x, y) が行き先のマスであり,−1000 ≤ x ≤ 1000 かつ −1000 ≤ y ≤ 1000 を満たす.

Output

各データセットについて,マス (0, 0) から行き先のマスまで移動するために必要なステップ数の最小値を 1 行に出力しなさい.

Sample Input

7
0 0
0 1
1 0
2 1
2 -1
-3 2
-1 -3

Output for the Sample Input

0
1
1
3
2
3
4