El Gomoku tradicional, o cinco en línea, se juega en un tablero pequeño y termina inmediatamente cuando se alinean cinco fichas del mismo color. Sin embargo, en el «Nuevo Gomoku», las reglas son diferentes. Las reglas del Nuevo Gomoku son las siguientes:

• El tablero es más grande, con un largo y ancho de $1000$.
• Los jugadores de fichas negras y blancas se turnan para colocar sus fichas, comenzando con el jugador negro. Una coordenada en la que ya se ha colocado una ficha no puede volver a ocuparse.
• Si exactamente $5$ fichas del mismo color están dispuestas formando una línea ininterrumpida de cinco fichas (horizontal, vertical o diagonalmente a $45^\circ/135^\circ$ respecto a la línea horizontal), se denomina un conjunto de cinco en línea. El juego no termina cuando un bando consigue un conjunto de cinco en línea.
• El juego termina cuando se alcanza el número predeterminado de movimientos.

Tu tarea es imprimir el número total de conjuntos de cinco en línea del jugador que acaba de colocar su ficha después de cada uno de los $n$ movimientos de la secuencia dada.

Entrada

Hay múltiples casos de prueba en un solo archivo de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene un entero $n$ ($1 \le n \le 10^4$), que indica el número de movimientos.
• Las siguientes $n$ líneas contienen cada una dos enteros $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) que representan las coordenadas del $i$-ésimo movimiento, garantizando que todas las coordenadas en el mismo conjunto de datos sean únicas.

Se garantiza que la suma total de $n$ en todos los casos de prueba no supera $10^4$, es decir, $\sum n \le 10^4$.

Salida

Para cada caso de prueba, imprime una sola línea con $n$ números, donde el $i$-ésimo número indica el número total de conjuntos de cinco en línea del jugador que acaba de colocar su ficha después del $i$-ésimo movimiento.

Ejemplo

Ejemplo 1

1
14
1 1
2 1
1 2
2 3
1 3
2 5
1 4
2 7
1 5
2 4
1 6
2 2
1 7
2 6

0 0 0 0 0 0 0 0 1 0 2 1 3 3