Traditional Gomoku, or five in a row, is played on a small board and ends immediately when five pieces of the same color are aligned. However, in "New Gomoku," the rules are different. The rules of New Gomoku are as follows:

• The board is larger, with a length and width of $1000$.
• Black and white players take turns placing their pieces, starting with the black player. A coordinate that has already been placed with a piece cannot be placed again.
• If exactly $5$ pieces of the same color are arranged to form an unbroken line of five pieces (horizontally, vertically, or diagonally at $45^\circ/135^\circ$ to the horizontal line), it is called a set of five in a row. The game does not end when one side gets a set of five in a row.
• The game ends when the predetermined number of moves is reached.

Your task is to output the total number of five in a row for the player who just placed their piece after each of the $n$ moves in the given sequence.

Input

There are multiple test cases in a single test file. The first line of the input contains a single integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases.

For each test case:

• The first line contains an integer $n$ ($1 \le n \le 10^4$), indicating the number of moves.
• The next $n$ lines each contain two integers $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) representing the coordinates of the $i$-th move, ensuring that all coordinates in the same data set are unique.

It is guaranteed that the total sum of $n$ over all test cases does not exceed $10^4$, i.e., $\sum n \le 10^4$.

Output

For each test case, output a single line with $n$ numbers, where the $i$-th number indicates the total number of five in a row for the player who just placed their piece after the $i$-th move.

Example

Sample 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