Traditionelles Gomoku, oder Fünf in einer Reihe, wird auf einem kleinen Brett gespielt und endet sofort, wenn fünf Steine derselben Farbe in einer Reihe liegen. Beim „Neuen Gomoku“ sind die Regeln jedoch anders. Die Regeln von Neues Gomoku lauten wie folgt:

• Das Spielbrett ist größer und hat eine Länge und Breite von $1000$.
• Der schwarze und der weiße Spieler setzen abwechselnd ihre Steine, beginnend mit dem schwarzen Spieler. Auf eine Koordinate, auf der bereits ein Stein liegt, kann kein weiterer Stein gesetzt werden.
• Wenn genau $5$ Steine derselben Farbe so angeordnet sind, dass sie eine ununterbrochene Linie aus fünf Steinen bilden (horizontal, vertikal oder diagonal im Winkel von $45^\circ/135^\circ$ zur Horizontalen), nennt man dies eine Fünferreihe. Das Spiel endet nicht, wenn eine Seite eine Fünferreihe erreicht.
• Das Spiel endet, wenn die vorher festgelegte Anzahl an Zügen erreicht ist.

Deine Aufgabe ist es, nach jedem der $n$ Züge in der gegebenen Zugfolge die Gesamtzahl der Fünferreihen für denjenigen Spieler auszugeben, der gerade seinen Stein gesetzt hat.

Eingabe

Es gibt mehrere Testfälle in einer einzigen Testdatei. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall gilt:

• Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 10^4$), die die Anzahl der Züge angibt.
• Die nächsten $n$ Zeilen enthalten jeweils zwei ganze Zahlen $x_i, y_i$ ($1 \le x_i, y_i \le 1000$), die die Koordinaten des $i$-ten Zuges darstellen, wobei sichergestellt ist, dass alle Koordinaten innerhalb desselben Datensatzes paarweise verschieden sind.

Es wird garantiert, dass die Gesamtsumme von $n$ über alle Testfälle $10^4$ nicht überschreitet, d. h. $\sum n \le 10^4$.

Ausgabe

Gib für jeden Testfall eine einzige Zeile mit $n$ Zahlen aus, wobei die $i$-te Zahl die Gesamtzahl der Fünferreihen für den Spieler angibt, der beim $i$-ten Zug gerade seinen Stein gesetzt hat.

Beispiel

Beispiel 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