Le Gomoku traditionnel, ou cinq à la suite, se joue sur un petit plateau et se termine immédiatement lorsque cinq pions de la même couleur sont alignés. Cependant, dans le « Nouveau Gomoku », les règles sont différentes. Les règles du Nouveau Gomoku sont les suivantes :

• Le plateau est plus grand, avec une longueur et une largeur de $1000$.
• Les joueurs noir et blanc placent leurs pions à tour de rôle, en commençant par le joueur noir. Une coordonnée où un pion a déjà été placé ne peut plus recevoir de pion.
• Si exactement $5$ pions de la même couleur sont disposés de manière à former une ligne ininterrompue de cinq pions (horizontalement, verticalement ou en diagonale à $45^\circ/135^\circ$ par rapport à l'horizontale), on appelle cela un alignement de cinq à la suite. La partie ne s'arrête pas lorsqu'un camp obtient un alignement de cinq à la suite.
• La partie se termine lorsque le nombre prédéterminé de coups est atteint.

Votre tâche consiste à afficher le nombre total d'alignements de cinq à la suite du joueur qui vient de placer son pion après chacun des $n$ coups de la séquence donnée.

Entrée

Il y a plusieurs cas de test dans un seul fichier de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient un entier $n$ ($1 \le n \le 10^4$), indiquant le nombre de coups.
• Les $n$ lignes suivantes contiennent chacune deux entiers $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) représentant les coordonnées du $i$-ème coup, en garantissant que toutes les coordonnées d'un même jeu de données sont uniques.

Il est garanti que la somme totale de $n$ sur l'ensemble des cas de test ne dépasse pas $10^4$, c'est-à-dire $\sum n \le 10^4$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant $n$ nombres, où le $i$-ème nombre indique le nombre total d'alignements de cinq à la suite du joueur qui vient de placer son pion après le $i$-ème coup.

Exemple

Exemple 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