Le Prof. Pang joue aux dames chinoises. Le plateau de jeu est identique à la figure ci-dessus. Il y a $n$ pions sur le plateau. Le Prof. Pang veut savoir combien de mouvements différents sont possibles sur le plateau actuel.

Un mouvement se compose de plusieurs étapes. Au début, le Prof. Pang doit choisir un pion $a$ à déplacer. À chaque étape, le Prof. Pang doit choisir un autre pion $b$ comme pivot, et déplacer le pion $a$ vers la position symétrique par rapport au pion $b$. (En un seul mouvement, le Prof. Pang ne peut pas changer son choix de $a$ entre les étapes. Si, après une étape, le pion $a$ revient à sa position initiale avant le mouvement, cette étape n'est pas autorisée.) Il existe plusieurs conditions concernant le pivot $b$ :

• Le segment reliant $a$ et $b$ doit être parallèle à l'un des axes de coordonnées. Note : Il y a trois axes sur le plateau hexagonal. L'un d'eux est horizontal et toute paire d'axes s'intersecte avec un angle de $\pi/3$.
• $a$ et $b$ n'ont pas besoin d'être adjacents.
• Il ne peut y avoir aucun pion supplémentaire autre que $b$ sur le segment reliant $a$ et sa position symétrique.
• La position symétrique doit se trouver sur le plateau hexagonal et ne pas être occupée par un autre pion.

Un mouvement doit comporter au moins une étape. Après la première étape, le Prof. Pang peut s'arrêter à tout moment. De plus, le Prof. Pang peut choisir n'importe quel pion sur le plateau comme pion mobile. Affichez le nombre de mouvements différents que le Prof. Pang peut effectuer. Deux mouvements sont différents si et seulement si les ensembles de positions de tous les pions sont différents après ces deux mouvements, c'est-à-dire que les pions sont indiscernables.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 100$) – le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 121$) – le nombre de pions.

Chacune des $n$ lignes suivantes contient deux entiers, indiquant la position d'un pion. Le premier nombre indique la ligne dans laquelle il se trouve, et le second nombre indique sa position dans cette ligne. Le comptage s'effectue de haut en bas et de gauche à droite, en commençant à 1.

Il est garanti que les positions des pions sont distinctes.

Sortie

Pour chaque cas de test, affichez un entier sur une ligne – le nombre de mouvements différents.

Exemple

Entrée 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

Sortie 1

0
1
2
6
13