会议难题

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

一场大型会议即将在柏林召开，共有 $n$ 位科学家参加。第 $i$ 位科学家会在第 $l_i$ 天到达、第 $r_i$ 天离开，因此其在场日期为闭区间 $[l_i,r_i]$。

部分科学家的国家已经确定。$c_i>0$ 表示第 $i$ 位科学家来自编号为 $c_i$ 的国家；$c_i=0$ 表示其国家尚未确定，组织者可以为这些科学家任意指定国家，国家编号没有额外限制。

如果一位科学家在其参会期间没有遇到任何来自不同国家的人，他就会感到不高兴。两位科学家只要在至少一天同时在场，就算相遇；到达日和离开日也计算在内。

组织者希望为所有 $c_i=0$ 的科学家指定国家，使不高兴的科学家数量尽可能多。请输出这个最大数量。

输入格式

本题包含多组测试数据。

第一行包含整数 $t$，表示测试数据组数。

每组数据的第一行包含整数 $n$。

接下来 $n$ 行，每行包含三个整数 $l_i,r_i,c_i$。

输出格式

对每组测试数据输出一行一个整数，表示不高兴科学家数量的最大值。

样例输入 1

2
4
1 10 30
5 6 30
6 12 0
1 1 0
4
1 2 1
2 3 0
3 4 0
4 5 2

样例输出 1

4
2

数据范围

• $1\le t\le100$；
• $1\le n\le500$，所有测试数据中 $n$ 的总和不超过 $500$；
• $1\le l_i\le r_i\le10^6$；
• $0\le c_i\le200$。