Il Gomoku tradizionale, o cinque in fila, si gioca su una piccola scacchiera e termina immediatamente quando cinque pedine dello stesso colore sono allineate. Tuttavia, nel "Nuovo Gomoku", le regole sono diverse. Le regole del Nuovo Gomoku sono le seguenti:

• La scacchiera è più grande, con una lunghezza e una larghezza pari a $1000$.
• I giocatori nero e bianco posizionano a turno le proprie pedine, iniziando dal giocatore nero. Una coordinata in cui è già stata posizionata una pedina non può essere occupata di nuovo.
• Se esattamente $5$ pedine dello stesso colore sono disposte in modo da formare una linea ininterrotta di cinque pedine (orizzontalmente, verticalmente o diagonalmente a $45^\circ/135^\circ$ rispetto alla linea orizzontale), questa viene chiamata una serie di cinque in fila. La partita non termina quando una parte ottiene una serie di cinque in fila.
• La partita termina quando viene raggiunto il numero predeterminato di mosse.

Il tuo compito è stampare il numero totale di serie di cinque in fila per il giocatore che ha appena posizionato la propria pedina dopo ciascuna delle $n$ mosse nella sequenza data.

Input

Ci sono più casi di test in un singolo file di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene un intero $n$ ($1 \le n \le 10^4$), che indica il numero di mosse.
• Le successive $n$ righe contengono ciascuna due interi $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) che rappresentano le coordinate della $i$-esima mossa, garantendo che tutte le coordinate nello stesso set di dati siano uniche.

È garantito che la somma totale di $n$ su tutti i casi di test non superi $10^4$, ovvero $\sum n \le 10^4$.

Output

Per ciascun caso di test, stampa una singola riga con $n$ numeri, dove l'$i$-esimo numero indica il numero totale di serie di cinque in fila per il giocatore che ha appena posizionato la propria pedina dopo la $i$-esima mossa.

Esempio

Esempio 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