秋のイルミネーション

四角形が大好きな人が多く住む四角町では、四角形の電光板を組み合わせたイルミネーションで町中を彩るお祭りが開催されます。この電光板は電気を流すと発光し、発光している板に接している板も発光します。したがって、電光板を何枚使っても、すべてがひとかたまりに接していれば電源がひとつで済むという優れものです。

お祭り実行委員会では、四角形を組み合わせたデザインを町民から募集し多数のイルミネーションを作成します。各イルミネーションは、デザインを構成する四角形の配置によって必要となる電源の個数が変わるため、必要な電源の個数を把握する作業に大きな手間がかかります。そこで、あなたは四角形の配置を調べ、必要な電源の個数を計算するプログラムを作成して実行委員会を手助けすることにしました。

イルミネーションの個数、各イルミネーションを構成する四角形の情報を入力とし、イルミネーションごとに必要な電源の個数を出力するプログラムを作成してください。重なっていたり接していたりする四角形を 1 つのまとまりと考え、1 つのまとまりに対して電源の個数は 1 つと数えてください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

N
M1
xa1 ya1 xb1 yb1 xc1 yc1 xd1 yd1
xa2 ya2 xb2 yb2 xc2 yc2 xd2 yd2
:
xaM1 yaM1 xbM1 ybM1 xcM1 ycM1 xdM1 ydM1
M2
:
:
MN
:
:

1 行目にイルミネーションの個数 N (1 ≤ N ≤ 100) が与えられます。続いて、N 個のイルミネーションの情報が与えられます。第 i のイルミネーションの情報として、イルミネーションを構成する四角形の個数 M_i (1 ≤ M_i ≤ 100) が１行に与えられます。続く M_i 行に j 個目の四角形の頂点 xa_j, ya_j, xb_j, yb_j, xc_j, yc_j, xd_j, yd_j (-1000 以上 1000 以下の整数) が与えられます。

入力される四角形の頂点座標は、時計回りの順に従って入力されます。ただし、入力データの四角形はすべて凸な四角形とします。

データセットの数は 10 を超えません。

Output

入力データセットごとに、イルミネーションごとに必要な電源の個数を出力します。出力する電源の個数は各イルミネーションが入力された順番に従ってください。

Sample Input

3
1
0 0 0 1 1 1 1 0
2
0 0 0 1 1 1 1 0
100 100 100 200 200 200 200 100
2
0 0 0 100 100 100 100 0
10 10 10 20 20 20 20 10
2
1
30 40 40 50 40 20 20 10
1
30 40 40 50 40 20 20 10
0

Output for the Sample Input

1
2
1
1
1