Tradisjonell Gomoku, eller fem på rad, spilles på et lite brett og avsluttes umiddelbart når fem brikker av samme farge ligger på linje. I «Nye Gomoku» er imidlertid reglene annerledes. Reglene for Nye Gomoku er som følger:

• Brettet er større, med en lengde og bredde på $1000$.
• Svart og hvit spiller bytter på å plassere brikkene sine, og svart spiller starter. En koordinat der det allerede er plassert en brikke, kan ikke brukes igjen.
• Hvis nøyaktig $5$ brikker av samme farge er plassert slik at de danner en ubrutt linje av fem brikker (horisontalt, vertikalt eller diagonalt i $45^\circ/135^\circ$ i forhold til den horisontale linjen), kalles det et sett med fem på rad. Spillet avsluttes ikke når en side får et sett med fem på rad.
• Spillet avsluttes når det forhåndsbestemte antallet trekk er nådd.

Din oppgave er å skrive ut det totale antallet fem på rad for spilleren som nettopp plasserte brikken sin etter hvert av de $n$ trekkene i den gitte sekvensen.

Inndata

Det er flere testtilfeller i én enkelt testfil. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^4$), som angir antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder et heltall $n$ ($1 \le n \le 10^4$), som angir antallet trekk.
• De neste $n$ linjene inneholder hver to heltall $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) som representerer koordinatene til det $i$-te trekket, og det er garantert at alle koordinater i samme datasett er unike.

Det er garantert at den totale summen av $n$ over alle testtilfeller ikke overstiger $10^4$, dvs. $\sum n \le 10^4$.

Utdata

For hvert testtilfelle, skriv ut én enkelt linje med $n$ tall, der det $i$-te tallet angir det totale antallet fem på rad for spilleren som nettopp plasserte brikken sin etter det $i$-te trekket.

Eksempel

Eksempel 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