AliceとBobは、$300 \times 300$ の2次元グリッド上でゲームを行っている。ボードはセルに分割されており、各セルは $1$ から $300$ の範囲の整数である $(x, y)$ 座標によって一意に識別される。

ボード上には異なるセルに2つのトークンが置かれている。Aliceが先攻である。各プレイヤーのターンでは、プレイヤーはトークンのうち1つを選び、そのトークンがあるセルの座標のうち一方を選び、その座標を正の量だけ減少させる。移動後のトークンは、もう一方のトークンを飛び越えたり、同じ位置に重なったりすることはできない。また、トークンはボード上にとどまらなければならない（したがって、両方の座標が正の値を維持する必要がある）。移動できなくなった最初のプレイヤーが負けとなる。両プレイヤーともどちらのトークンも動かせることに注意せよ。

複数のゲームの開始状態が与えられる。それぞれのゲームについて、Aliceが最初に行える勝利となる移動の数を計算せよ。

入力

入力の最初の行には、解析するゲームの数を示す整数 $n$ ($1 \le n \le 10^5$) が含まれる。 続く $n$ 行の各行には、4つの整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2, y_1, y_2 \le 300$ であり、$x_1 = x_2$ または $y_1 = y_2$ が成り立つ) が含まれる。これは、トークンが $(x_1, y_1)$ と $(x_2, y_2)$ にある1つのゲームの開始状態を表している。

出力

$n$ 行を出力せよ。各行に、Aliceが最初に行える勝利となる移動の数を1つの整数で出力せよ。入力された順序で出力すること。

入出力例

入力 1

5
6 6 6 3
6 6 2 2
1 6 3 1
3 6 1 3
6 3 1 5

出力 1

3
0
1
1
0