Figura 1. Tablero de damas chinas

El Prof. Pang está jugando a las damas chinas. El tablero de juego es el mismo que se muestra en la figura anterior. Hay $n$ fichas en el tablero. El Prof. Pang quiere saber cuántos movimientos diferentes se pueden realizar en el tablero actual.

Un movimiento consiste en varios pasos. Al principio, el Prof. Pang debe elegir una ficha $a$ para mover. En cada paso, el Prof. Pang debe elegir otra ficha $b$ como pivote y mover la ficha $a$ a la posición simétrica respecto a la ficha $b$. (En un mismo movimiento, el Prof. Pang no puede cambiar su elección de $a$ entre pasos. Si después de un paso, la ficha $a$ regresa a su posición anterior al movimiento, este paso no está permitido). Existen varias condiciones sobre el pivote $b$:

• El segmento que conecta $a$ y $b$ debe ser paralelo a uno de los ejes de coordenadas. Nota: Hay tres ejes en el tablero hexagonal. Uno de ellos es horizontal y cualquier par de ejes se interseca en un ángulo de $\pi/3$.
• $a$ y $b$ no necesitan ser adyacentes.
• No puede haber fichas adicionales aparte de $b$ en el segmento que conecta $a$ y su posición simétrica.
• La posición simétrica debe estar dentro del tablero hexagonal y no debe estar ocupada por ninguna otra ficha.

Un movimiento debe tener al menos un paso. Después del primer paso, el Prof. Pang puede detenerse en cualquier momento que desee. Además, el Prof. Pang puede elegir cualquier ficha del tablero como la ficha a mover. Imprima el número de movimientos diferentes que el Prof. Pang puede realizar. Dos movimientos son diferentes si y solo si los conjuntos de posiciones de todas las fichas son diferentes después de estos dos movimientos, es decir, las fichas son indistinguibles.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 100$) – el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($1 \le n \le 121$) – el número de fichas.

Cada una de las siguientes $n$ líneas contiene dos enteros, que indican la posición de una ficha. El primer número indica en qué fila se encuentra y el segundo número indica cuál de esa fila es. Se cuentan de arriba a abajo y de izquierda a derecha, comenzando desde 1.

Se garantiza que las posiciones de las fichas son diferentes.

Salida

Para cada caso de prueba, imprima un entero en una línea: el número de movimientos diferentes.

Ejemplos

Entrada 1

1
1
1 1

Salida 1

0

Entrada 2

1
2
1 1
2 1

Salida 2

1

Entrada 3

1
2
9 4
9 6

Salida 3

2

Entrada 4

1
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4

Salida 4

6

Entrada 5

1
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

Salida 5

13