题目描述

Bob 和 Alice 在一起了，他们坐在未名湖畔数着天上的星星。

天上有 $n$ 颗星星，每颗星星有二维坐标 $(x_i,\ y_i)$ ，还有一个属性值 $z_i$ ，若两颗星星 $A,\ B$ 满足 $x_A < x_B$ 且 $y_A < y_B$ 且 $z_A < z_B$ ，则这两颗星星可以配成一对，每颗星星最多只能在一对之中，求最多能配成多少对星星。

输入格式

一行一个整数 $T$ ，代表数据组数.

接下来 $T$ 组数据，对于每组数据：

第一行一个正整数 $n$ ，表示星星的个数。

接下来 $n$ 行，每行 $3$ 个整数 $x_i,\ y_i,\ z_i$ ，表示一颗星星。

输出格式

输出共 $T$ 行，每行一个整数，表示答案。

样例

样例输入

2
2
1 1 0
2 2 1
2
1 1 1
2 2 1

样例输出

1
0

数据范围与提示

$1 \le n \le 10^5$

$0 \le x_i,\ y_i \le 10^9$

$z_i \in \{0,\ 1\}$

保证所有测试点中 $n$ 的和 $\le 3 \cdot 10^5$ 。