Problem Statement

There are $N$ people with distinct surnames, and the surname of the $i$-th person has parameters $(X_i, Y_i, Z_i)$. Different surnames may have identical parameters. The following event occurs $N - 1$ times.

• Two people become parents and one child appears. The two parents die. The child chooses the stronger of the two parents' surnames as their own. A surname with parameters $(x_1, y_1, z_1)$ is stronger than a surname with parameters $(x_2, y_2, z_2)$ if $x_1 > x_2$, $y_1 > y_2$, and $z_1 > z_2$ all hold. If neither parent's surname is stronger than the other's, the child randomly chooses one of the two parents' surnames.

Find the number of people among the $N$ people whose surname can be the surname of the last remaining person.

You are given $T$ test cases; solve each one.

Constraints

• $1 \le T \le 2 \times 10^5$
• $2 \le N \le 2 \times 10^5$
• $1 \le X_i, Y_i, Z_i \le N$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

Output

Output $T$ lines.

The $i$-th line should contain the number of people whose surname can be the surname of the last remaining person for the $i$-th test case.