Prof. Pang 正在玩中國跳棋。遊戲棋盤如上圖所示。棋盤上有 $n$ 枚棋子。Prof. Pang 想知道在當前棋盤上總共有多少種不同的移動方式。

一次移動包含若干個步驟。首先，Prof. Pang 需要選擇一枚棋子 $a$ 進行移動。在每一個步驟中，Prof. Pang 需要選擇另一枚棋子 $b$ 作為軸心，並將棋子 $a$ 移動到關於棋子 $b$ 對稱的位置。（在一次移動中，Prof. Pang 在各個步驟之間不能更換他所選擇的棋子 $a$。如果某個步驟執行後，棋子 $a$ 回到了移動開始前的位置，則該步驟是不允許的。）關於軸心 $b$ 有以下幾個條件：

• 連接 $a$ 和 $b$ 的線段必須平行於其中一個座標軸。注意：六角形棋盤上有三條座標軸。其中一條是水平的，且任意兩條軸之間的夾角為 $\pi/3$。
• $a$ 和 $b$ 不需要相鄰。
• 在連接 $a$ 和其對稱位置的線段上，除了 $b$ 之外不能有其他棋子。
• 對稱位置必須位於六角形棋盤內，且不能被其他任何棋子佔據。

一次移動必須至少包含一個步驟。在第一個步驟之後，Prof. Pang 可以隨時停止。此外，Prof. Pang 可以選擇棋盤上的任意棋子作為移動的棋子。請輸出 Prof. Pang 可以做出的不同移動總數。若且唯若兩次移動後所有棋子的位置集合不同時，這兩次移動才被視為不同，即棋子是無法區分的。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 100$)，代表測試資料的組數。 對於每一組測試資料，第一行包含一個整數 $n$ ($1 \le n \le 121$)，代表棋子的數量。 接下來的 $n$ 行，每行包含兩個整數，表示一枚棋子的位置。第一個數字表示它所在的行數，第二個數字表示它是該行中的第幾個。行數與位置皆由上到下、由左到右從 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