Tradycyjne Gomoku, czyli pięć w rzędzie, rozgrywane jest na małej planszy i kończy się natychmiast, gdy pięć kamieni tego samego koloru zostanie ułożonych w jednej linii. Jednak w „Nowym Gomoku” zasady są inne. Zasady Nowego Gomoku są następujące:

• Plansza jest większa, a jej długość i szerokość wynoszą $1000$.
• Gracze czarny i biały na zmianę kładą swoje kamienie, zaczynając od gracza czarnego. Na współrzędnych, na których położono już kamień, nie można położyć kolejnego.
• Jeśli dokładnie $5$ kamieni tego samego koloru tworzy nieprzerwaną linię pięciu kamieni (poziomo, pionowo lub ukośnie pod kątem $45^\circ/135^\circ$ do linii poziomej), nazywamy to układem pięciu w rzędzie. Gra nie kończy się, gdy któraś ze stron uzyska układ pięciu w rzędzie.
• Gra kończy się po osiągnięciu z góry określonej liczby ruchów.

Twoim zadaniem jest wypisanie łącznej liczby układów pięciu w rzędzie dla gracza, który właśnie położył swój kamień, po każdym z $n$ ruchów w podanej sekwencji.

Wejście

W jednym pliku testowym znajduje się wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 10^4$), oznaczającą liczbę ruchów.
• Kolejne $n$ wierszy zawiera po dwie liczby całkowite $x_i, y_i$ ($1 \le x_i, y_i \le 1000$), reprezentujące współrzędne $i$-tego ruchu; wszystkie współrzędne w tym samym zestawie danych są unikalne.

Gwarantuje się, że łączna suma $n$ po wszystkich przypadkach testowych nie przekracza $10^4$, tzn. $\sum n \le 10^4$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ liczb, gdzie $i$-ta liczba oznacza łączną liczbę układów pięciu w rzędzie gracza, który właśnie położył swój kamień po $i$-tym ruchu.

Przykład

Przykład 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