J. Temperance
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
In this world, only the green ones never let me down.
— Chen Loong

The renowned farmer Chen Loong discovered that a rational planting density could raise production.

Now, the farm can be viewed as a three-dimensional coordinate system, and a plant can be seen as a point in it. There are $$$n$$$ different plants $$$A_i=(x_i,y_i,z_i)$$$. For each plant $$$A_i$$$, its density is defined as follows.

  • Suppose there are $$$a$$$, $$$b$$$, and $$$c$$$ plants other than $$$A_i$$$ with the same $$$x$$$, $$$y$$$, or $$$z$$$ coordinates as $$$A_i$$$, respectively. Then, the density of $$$A_i$$$ is $$$\max\{a,b,c\}$$$.

Since Chen Loong's plants love involution, he decides to remove some plants with less density. Please answer the minimum number of plants that need to be removed such that each of the remaining plants has a density greater than or equal to $$$k$$$. Note that after removing a point, the density of other plants may change. In particular, removing all plants is always considered valid.

You need to solve for $$$k=0,1,\ldots,n-1$$$ respectively.

Input

The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1\le T\le 2 \times 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1 \le n\le 10^5$$$) — the number of plants.

In the next $$$n$$$ lines, the $$$i$$$-th line contains three integers $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ ($$$1 \le x_i,y_i,z_i \le 10^5$$$) — the coordinates of each plant.

It is guaranteed that the coordinates of the $$$n$$$ plants are distinct.

It is guaranteed that the sum of $$$n$$$ among $$$T$$$ test cases does not exceed $$$2\times 10^5$$$.

Output

For each test case, output $$$n$$$ integers in a line, representing the answers for $$$k=0,1,\ldots,n-1$$$.

Example
Input
2
5
1 1 1
1 1 2
1 1 3
2 3 5
2 2 4
3
1 1 1
2 2 2
3 3 3
Output
0 0 2 5 5
0 3 3