Cờ Caro truyền thống (Gomoku), hay năm quân thẳng hàng, được chơi trên một bàn cờ nhỏ và kết thúc ngay lập tức khi có năm quân cờ cùng màu xếp thẳng hàng. Tuy nhiên, trong "Cờ Caro Mới" (New Gomoku), luật chơi lại khác. Luật của Cờ Caro Mới như sau:

• Bàn cờ lớn hơn, với chiều dài và chiều rộng đều bằng $1000$.
• Người chơi quân đen và quân trắng lần lượt đặt quân cờ của mình, bắt đầu từ người chơi quân đen. Một tọa độ đã có quân cờ thì không thể đặt lại lần nữa.
• Nếu có đúng $5$ quân cờ cùng màu được xếp thành một đường thẳng liên tiếp gồm năm quân cờ (theo chiều ngang, chiều dọc, hoặc đường chéo tạo góc $45^\circ/135^\circ$ so với đường nằm ngang), thì nó được gọi là một bộ năm quân thẳng hàng. Trò chơi không kết thúc khi một bên đạt được một bộ năm quân thẳng hàng.
• Trò chơi kết thúc khi đạt đến số nước đi đã được định trước.

Nhiệm vụ của bạn là in ra tổng số bộ năm quân thẳng hàng của người chơi vừa đặt quân cờ sau mỗi nước đi trong chuỗi $n$ nước đi đã cho.

Dữ liệu vào

Có nhiều bộ test trong một tệp dữ liệu vào. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ test.

Với mỗi bộ test:

• Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^4$), cho biết số nước đi.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) biểu thị tọa độ của nước đi thứ $i$, đảm bảo rằng tất cả các tọa độ trong cùng một bộ dữ liệu đều là duy nhất.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $10^4$, tức là $\sum n \le 10^4$.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng duy nhất gồm $n$ số, trong đó số thứ $i$ cho biết tổng số bộ năm quân thẳng hàng của người chơi vừa đặt quân cờ sau nước đi thứ $i$.

Ví dụ

Ví dụ 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