傳統的五子棋（Gomoku）是在一個較小的棋盤上進行的，當同一種顏色的五顆棋子連成一線時遊戲立即結束。然而，在「新五子棋」（New Gomoku）中，規則有所不同。新五子棋的規則如下：

• 棋盤更大，長度和寬度均為 $1000$。
• 黑方和白方輪流落子，由黑方先手。已經落子的座標不能重複落子。
• 如果恰好有 $5$ 顆同色棋子排成一條不間斷的五子連線（水平、垂直或與水平線呈 $45^\circ/135^\circ$ 的對角線），則稱其為一組五子連珠。當某一方獲得五子連珠時，遊戲不會結束。
• 當達到預定的落子步數時，遊戲結束。

你的任務是，在給定的 $n$ 步落子序列中，在每一步落子之後，輸出剛剛落子的玩家所擁有的五子連珠的總數。

輸入格式

單個測試檔案中包含多組測試資料。輸入的第一行包含一個整數 $T$（$1 \le T \le 10^4$），表示測試資料的組數。

對於每組測試資料：

• 第一行包含一個整數 $n$（$1 \le n \le 10^4$），表示落子的步數。
• 接下來的 $n$ 行，每行包含兩個整數 $x_i, y_i$（$1 \le x_i, y_i \le 1000$），表示第 $i$ 步落子的座標，保證同一組資料中的所有座標都是互不相同的。

保證所有測試資料的 $n$ 之和不超過 $10^4$，即 $\sum n \le 10^4$。

輸出格式

對於每組測試資料，輸出一行，包含 $n$ 個數字，其中第 $i$ 個數字表示在第 $i$ 步落子之後，剛剛落子的玩家所擁有的五子連珠的總數。

範例

範例 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