問題文

セグメントツリーのように区切られた釣り堀があります。
岩井星人さんはここで仲間とセグメント釣りをする約束をしていましたが、遅刻しそうになっています。

岩井星人さんが遅刻しないよう、釣り堀内を移動する最小コストを調べましょう。

$xy$ 平面上の $x$ 座標と $y$ 座標がともに非負である領域に、以下のような規則でタイルが配置されています。

• 非負整数対 $(i, j)$ に対し、正方形 $A_{i, j} = \{(x, y) ~ | ~ i \leq x \leq i + 1 ~ \land ~ j \leq y \leq j + 1\}$ は $1$ つのタイルに含まれる。
• $2$ つの非負整数対 $(i, j), (i', j')$ について、 $j = j'$ かつ $\lfloor i / 2^j \rfloor = \lfloor i' / 2^{j'} \rfloor$ を満たすとき（かつそのときに限り） $A_{i, j}$ と $A_{i', j'}$ は同じタイルに含まれる。

ただし、タイルは境界を含むものとし、共通部分が正の面積をもつような $2$ つの異なるタイルは存在しないとします。

岩井星人さんは、はじめ座標 $(S_x + 0.5, S_y + 0.5)$ にいます。
岩井星人さんは、以下の行動を $0$ 回以上の好きな回数行うことができます。

• 岩井星人さんが座標 $(x, y)$ にいるとき、 座標 $(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)$ のいずれかに移動する。ただし、移動先の $x$ 座標と $y$ 座標のいずれかが負になるような移動はできない。

岩井星人さんは、異なるタイルを通るたびにコストを $1$ 支払います。
座標 $(T_x + 0.5, T_y + 0.5)$ に到達するために岩井星人さんが支払う必要のあるコストの総和の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力される値はすべて整数
• $1 \leq T \leq 10^5$
• $0 \leq S_x, S_y, T_x, T_y \leq 10^{18}$
• $(S_x, S_y) \ne (T_x, T_y)$

入力

入力は以下の形式で標準入力から与えられる。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$S_x$ $S_y$ $T_x$ $T_y$

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

サンプル

3
1 0 4 1
2 4 15 4
0 0 1000000000000000000 1000000000000000000

3
0
1000000000000000000