Prof. Pang はチャイニーズ・チェッカーをプレイしています。ゲーム盤は上の図と同じです。

Figure 1. チャイニーズ・チェッカーのゲーム盤

盤上には $n$ 個のチェッカーがあります。Prof. Pang は、現在の盤面において何通りの異なる手が存在するかを知りたいと考えています。

1 回の「手」は、いくつかのステップで構成されます。まず、Prof. Pang は動かすチェッカー $a$ を 1 つ選択する必要があります。各ステップにおいて、Prof. Pang は別のチェッカー $b$ をピボットとして選択し、チェッカー $a$ をチェッカー $b$ に関して対称な位置に移動させます。（1 回の手の中で、ステップの間に動かすチェッカー $a$ を変更することはできません。あるステップの後、チェッカー $a$ がその手を動かす前の位置に戻る場合、そのステップは許可されません。）ピボット $b$ に関しては、いくつかの条件があります。

• $a$ と $b$ を結ぶ線分は、座標軸のいずれかと平行である必要があります。注：六角形の盤面には 3 つの軸があります。そのうちの 1 つは水平であり、どの 2 つの軸も $\pi/3$ の角度で交差しています。
• $a$ と $b$ は隣接している必要はありません。
• $a$ とその対称位置を結ぶ線分上に、$b$ 以外のチェッカーが存在してはなりません。
• 対称位置は六角形の盤面上にあり、かつ他のチェッカーによって占有されていない必要があります。

1 回の手は少なくとも 1 つのステップを含まなければなりません。最初のステップの後、Prof. Pang はいつでも好きな時に止めることができます。また、Prof. Pang は盤上のどのチェッカーでも動かすチェッカーとして選択できます。Prof. Pang が行える異なる手の数を求めてください。2 つの手が異なるとは、それらの手を指した後のすべてのチェッカーの位置の集合が異なる場合を指します。つまり、チェッカーは区別できません。

入力

最初の行には整数 $T$ ($1 \le T \le 100$) が含まれ、テストケースの数を表します。 各テストケースについて、最初の行には整数 $n$ ($1 \le n \le 121$) が含まれ、チェッカーの数を表します。

続く $n$ 行のそれぞれには、チェッカーの位置を示す 2 つの整数が含まれます。最初の数字はそのチェッカーが何行目にあるかを示し、2 番目の数字はその行の何番目にあるかを示します。これらは上から下へ、左から右へと 1 から数えます。

チェッカーの位置はすべて異なることが保証されています。

出力

各テストケースについて、異なる手の数を 1 行に出力してください。

入出力例

入力 1

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

出力 1

0
1
2
6
13