Hefðbundið Gomoku, eða fimm í röð, er spilað á litlu borði og lýkur samstundis þegar fimm steinar af sama lit liggja í beinni línu. Hins vegar eru reglurnar öðruvísi í „Nýju Gomoku“. Reglurnar í Nýju Gomoku eru sem hér segir:

• Borðið er stærra, með lengd og breidd upp á $1000$.
• Svarti og hvíti leikmaðurinn skiptast á að setja niður steina sína, og byrjar sá svarti. Ekki er hægt að setja stein aftur á hnit þar sem steinn hefur þegar verið settur.
• Ef nákvæmlega $5$ steinar af sama lit raðast þannig að þeir myndi óslitna línu fimm steina (lárétt, lóðrétt eða á ská í $45^\circ/135^\circ$ horni við láréttu línuna), kallast það samstæða af fimm í röð. Leiknum lýkur ekki þegar annar hvor aðilinn fær fimm í röð.
• Leiknum lýkur þegar fyrirfram ákveðnum fjölda leikja er náð.

Verkefni þitt er að prenta heildarfjölda samstæða af fimm í röð hjá leikmanninum sem var að ljúka við að setja niður stein sinn eftir hvern af $n$ leikjunum í gefnu rununni.

Inntak

Það eru mörg prófunartilfelli í einni prófunarskrá. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilfella.

Fyrir hvert prófunartilfelli:

• Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 10^4$), sem gefur til kynna fjölda leikja.
• Næstu $n$ línur innihalda hver um sig tvær heiltölur $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) sem tákna hnit $i$-ta leiksins, og tryggt er að öll hnit í sama gagnasetti séu ólík.

Tryggt er að heildarsumma $n$ yfir öll prófunartilfelli fari ekki yfir $10^4$, þ.e. $\sum n \le 10^4$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina línu með $n$ tölum, þar sem $i$-ta talan gefur til kynna heildarfjölda samstæða af fimm í röð hjá leikmanninum sem var að setja niður stein sinn eftir $i$-ta leikinn.

Dæmi

Dæmi 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