一场大型非自然科学会议即将在贝尔兰召开!总共有来自世界各地的 $$$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