← 返回题目列表

Codeforces · 1250/D

D. 会议问题

中文机器翻译题面 查看原题

一场大型非自然科学会议即将在贝尔兰召开!总共有来自世界各地的 $$$n$$$ 科学家提出了申请。他们都指明了参加会议的时间段:两个整数$$$l_i$$$、$$$r_i$$$——到达日期和离开日期。

此外,一些科学家已经表明了他们的国家,而另一些科学家则不愿意这样做。因此,每个科学家也有一个值 $$$c_i$$$,其中:

- $$$c_i > 0$$$,如果科学家来自国家 $$$c_i$$$(所有国家编号从 $$$1$$$ 到 $$$200$$$);
- $$$c_i = 0$$$,如果科学家不想指明国家/地区。

大家都知道与其他国家的代表聊天很有趣而且很有用!如果会议参与者在逗留期间不能见到其他国家的人,她将会感到不安。您可以在整个住宿期间与他人见面,包括抵达当天和离开当天。

会议组织者需要做好最坏的打算!他们感兴趣的是最大的数字 $$$x$$$,即在所有参加会议的人中,有可能恰好 $$$x$$$ 会感到不安。

帮助组织者找到最多数量的心烦意乱的科学家。

输入

输入的第一行包含整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是测试用例。

每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 注册会议参与者的数量。

接下来的 $$$n$$$ 行如下,每行包含三个整数 $$$l_i$$$, $$$r_i$$$, $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^6$$$, $$$0 \le c_i \le 200$$$) — 抵达日期、出发日期和国家/地区(或事实上,没有指出)第 $$$i$$$ 参与者。

输入中所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。

输出

输出 $$$t$$$ 整数 — 每个测试用例心烦意乱的科学家的最大数量。

示例

输入 #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