Traditionell Gomoku, eller fem i rad, spelas på ett litet bräde och slutar omedelbart när fem pjäser av samma färg ligger i rad. I "Nya Gomoku" är reglerna dock annorlunda. Reglerna för Nya Gomoku är följande:

• Brädet är större, med en längd och bredd på $1000$.
• Svart och vit spelare turas om att placera sina pjäser, med början hos den svarta spelaren. En koordinat där det redan har placerats en pjäs kan inte användas igen.
• Om exakt $5$ pjäser av samma färg är placerade så att de bildar en obruten linje av fem pjäser (horisontellt, vertikalt eller diagonalt i $45^\circ/135^\circ$ mot horisontallinjen), kallas det en uppsättning av fem i rad. Spelet tar inte slut när en sida får en uppsättning av fem i rad.
• Spelet slutar när det förutbestämda antalet drag har uppnåtts.

Din uppgift är att skriva ut det totala antalet fem i rad för den spelare som nyss placerade sin pjäs efter vart och ett av de $n$ dragen i den givna sekvensen.

Indata

Det finns flera testfall i en enda testfil. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T \le 10^4$), vilket anger antalet testfall.

För varje testfall:

• Den första raden innehåller ett heltal $n$ ($1 \le n \le 10^4$), vilket anger antalet drag.
• De följande $n$ raderna innehåller var och en två heltal $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) som representerar koordinaterna för det $i$:te draget, där alla koordinater i samma datamängd garanteras vara unika.

Det garanteras att den totala summan av $n$ över alla testfall inte överstiger $10^4$, dvs. $\sum n \le 10^4$.

Utdata

För varje testfall, skriv ut en enda rad med $n$ tal, där det $i$:te talet anger det totala antalet fem i rad för den spelare som nyss placerade sin pjäs efter det $i$:te draget.

Exempel

Exempel 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