Glyph Yuji は旅行してさまざまな国で字形を発見することが大好きです。数年の旅行の後、Glyph は Lollipop と Boomerang の 2 国で見つけた字形に類似点があることに気付きました。この 2 か所の手書き体系は非常に似ており、手書きに使う字形はすべて直角で構成された形です。

直角で構成された字形は、2 次元ユークリッド平面上の単純多角形として表せます。多角形のすべての辺は、座標軸に平行または垂直です。

Lollipop と Boomerang で使われる 2 言語を詳しく調べた Glyph は、次を観察しました。(1) Lollipop の字形は通常 Boomerang の字形より大きい。(2) 各言語にはちょうど $n$ 個の異なる字形があり、それらは一対一に対応する。

しかし Glyph は、Lollipop のどの字形が Boomerang のどの字形に対応するか知りません。この対応を調べるため、まず各字形を単純多角形で記述します。

図 1：Lollipop 国の字形（左）、対応する Boomerang 国の字形（中央）、可能な平行移動領域（右）。（左下の角を $(0,0)$ とします。）

厳密には、領域 $B$ と点 $(x,y)$ に対して、Glyph は $B+(x,y)$ を集合 $B+(x,y):=\{(b_x+x,b_y+y)\mid(b_x,b_y)\in B\}$ と定義します。Lollipop の字形 $L$ と Boomerang の字形 $B$ の各組について、「平行移動面積」 $\operatorname{tr}(L,B)$ を領域 $\operatorname{tr}(L,B):=\{(x,y)\mid B+(x,y)\subseteq L\}$ の面積と定義します。例は図 1 を参照してください。

Glyph Yuji は、2 言語の本当の対応は、すべての対応する字形の組の平行移動面積の合計を最大にすると考えています。この定義では、字形の組の平行移動面積が 0 になる場合もあることに注意してください。Glyph がこの値を求めるのを手伝えますか？

入力

1 行目には、テストケース数を表す整数 $T$ が含まれます。

各テストケースは整数 $n$ で始まり、その後に $2n$ 行が続きます。最初の $n$ 行は Lollipop 言語の字形を表す $n$ 個の直角形状を記述し、続く $n$ 行は Boomerang 言語の字形を表す $n$ 個の直角形状を記述します。

直角形状を記述する $i$ 行目には、頂点数を表す整数 $m_i$ に続いて、時計回りまたは反時計回りの順で $m_i$ 組の整数座標が与えられます。

• $1\le T\le4$

• $1\le n\le30$

• $4\le m_i\le200$

• すべての座標 $(x,y)$ について $0\le x,y\le1000$。

• すべての直角形状は、有効で退化していない単純多角形です。

出力

各テストケースについて、対応する組の平行移動面積の合計の最大値を表す整数を 1 つだけ含む行を出力してください。答えが必ず整数であることを示せます。

入出力例

入力 1

2
1
10 0 0 0 10 2 10 2 12 6 12 6 8 2 8 2 4 6 4 6 0
8 0 0 0 3 2 3 2 2 1 2 1 1 2 1 2 0
2
5 0 0 0 2 0 5 5 5 5 0
4 0 0 3 0 3 6 0 6
4 0 0 1 0 1 2 0 2
4 0 0 0 1 2 1 2 0

出力 1

6
20