C: オセロ

問題

オセロの盤面を用意する. 盤面は左上が $(1,1)$ , 右下が $(8,8)$ と表記する. ここで用意する盤面は, 以下のように, $(5,4)$ の黒の石がない.

........
........
........
...ox...
....o...
........
........
........

黒石:x 白石:o
8x8の盤面
この状態から, 黒が先手でオセロを開始する.

AORイカちゃんは, 以下のルールで $q$ 回遊ぶ.

左上を $a$ 行目 $b$ 列目のマス, 右下を $c$ 行目 $d$ 列目のマスとした, マス目に沿った長方形領域が与えられる.

AORイカちゃんは, この長方形領域に含まれる石の数を最大化するように, オセロのルール(参考:Wikipedia　オセロ )にのっとり黒石と白石を交互に置いていく.
これ以上石が置けなくなったとき(白石黒石ともにパスするしかない状態やすべての盤面が埋まった状態のとき), ゲームを終了する.

それぞれのゲームで, その領域に含まれる石の数を最大化したときの石の数を出力せよ.
なお, 入力や出力の回数が多くなることがあるため, 入出力には高速な関数を用いることを推奨する.

制約

• $1 \leq q \leq 10^{5}$
• $1 \leq a \leq c \leq 8$
• $1 \leq b \leq d \leq 8$

入力形式

入力は以下の形式で与えられる.

$q$
$a_1\ b_1\ c_1\ d_1$
$a_2\ b_2\ c_2\ d_2$
$\vdots$
$a_q\ b_q\ c_q\ d_q$

出力

それぞれのゲームで, その領域に含まれる, 石の数を最大化したときの石の数を出力せよ. また, 末尾に改行も出力せよ.

サンプル

サンプル入力 1

3
1 1 8 8
2 4 3 8
8 8 8 8

サンプル出力 1

48
7
1