Prof. Pang gra w chińskie warcaby. Plansza do gry jest taka sama jak na powyższym rysunku. Na planszy znajduje się $n$ pionków. Prof. Pang chce wiedzieć, ile różnych ruchów można wykonać na obecnej planszy.

Jeden ruch składa się z kilku kroków. Na początku Prof. Pang musi wybrać jeden pionek $a$, który chce przesunąć. W każdym kroku Prof. Pang musi wybrać inny pionek $b$ jako punkt obrotu i przesunąć pionek $a$ na pozycję symetryczną względem pionka $b$. (W trakcie jednego ruchu Prof. Pang nie może zmienić wyboru pionka $a$ pomiędzy krokami. Jeśli po wykonaniu kroku pionek $a$ wróci na swoją pozycję sprzed ruchu, taki krok jest niedozwolony.) Istnieje kilka warunków dotyczących punktu obrotu $b$:

• Odcinek łączący $a$ i $b$ musi być równoległy do jednej z osi układu współrzędnych. Uwaga: na planszy heksagonalnej istnieją trzy osie. Jedna z nich jest pozioma, a każda para osi przecina się pod kątem $\pi/3$.
• $a$ i $b$ nie muszą być sąsiadami.
• Na odcinku łączącym $a$ i jego pozycję symetryczną nie mogą znajdować się żadne dodatkowe pionki poza $b$.
• Pozycja symetryczna musi znajdować się na planszy heksagonalnej i nie może być zajęta przez żaden inny pionek.

Ruch musi składać się z co najmniej jednego kroku. Po pierwszym kroku Prof. Pang może zatrzymać się w dowolnym momencie. Prof. Pang może wybrać dowolny pionek na planszy jako pionek poruszający się. Wypisz liczbę różnych ruchów, które może wykonać Prof. Pang. Dwa ruchy są różne wtedy i tylko wtedy, gdy zbiory pozycji wszystkich pionków po wykonaniu tych dwóch ruchów są różne, tzn. pionki są nierozróżnialne.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$) – liczbę zestawów danych. Dla każdego zestawu danych, pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 121$) – liczbę pionków.

Każda z kolejnych $n$ linii zawiera dwie liczby całkowite określające pozycję pionka. Pierwsza liczba wskazuje, w którym rzędzie znajduje się pionek, a druga liczba wskazuje, który jest to pionek w tym rzędzie. Liczenie odbywa się od góry do dołu i od lewej do prawej, zaczynając od 1.

Gwarantuje się, że pozycje pionków są różne.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę całkowitą – liczbę różnych ruchów.

Przykład

Wejście 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

Wyjście 1

0
1
2
6
13