CF1250D.Conference Problem

A large-scale conference on unnatural sciences is going to be held soon in Berland! In total, $n$ scientists from all around the world have applied. All of them have indicated a time segment when they will attend the conference: two integers $l_i$, $r_i$ — day of arrival and day of departure.

Also, some of the scientists have indicated their country, while some preferred not to. So, each scientist also has a value $c_i$, where:

• $c_i \gt 0$, if the scientist is coming from country $c_i$ (all countries are numbered from $1$ to $200$);
• $c_i = 0$, if the scientist preferred to not indicate the country.

Everyone knows that it is interesting and useful to chat with representatives of other countries! A participant of the conference will be upset if she will not meet people from other countries during the stay. It is possible to meet people during all time of stay, including the day of arrival and the day of departure.

Conference organizers need to be ready for the worst! They are interested in the largest number $x$, that it is possible that among all people attending the conference exactly $x$ will be upset.

Help the organizers to find the maximum number of upset scientists.

一场关于“非自然科学”的大型国际会议即将在贝尔兰举行！总共有 $n$ 位来自世界各地的科学家报名参会。每位科学家均指定了其参会的时间区间：两个整数 $l_i$ 和 $r_i$，分别表示其抵达日期和离开日期。

此外，部分科学家注明了自己所属的国家，而另一些则选择不透露。因此，每位科学家还对应一个值 $c_i$，其含义如下：

• 若 $c_i > 0$，则该科学家来自编号为 $c_i$ 的国家（所有国家编号为 $1$ 至 $200$）；
• 若 $c_i = 0$，则该科学家选择不透露国籍。

众所周知，与来自其他国家的代表交流既有趣又有益！一位参会者若在其整个停留期间（包括抵达日和离开日）都未能遇到任何其他国籍的参会者，则会感到沮丧。

会议组织者需为最坏情况做好准备！他们关心的是最大的整数 $x$，使得有可能恰好有 $x$ 位参会者感到沮丧。

请帮助组织者找出可能感到沮丧的科学家的最大人数。

The first line of the input contains integer $t$ ($1 \le t \le 100$) — number of test cases. Then the test cases follow.

The first line of each test case contains integer $n$ ($1 \le n \le 500$) — the number of registered conference participants.

Next $n$ lines follow, each containing three integers $l_i$, $r_i$, $c_i$ ($1 \le l_i \le r_i \le 10^6$, $0 \le c_i \le 200$) — the day of arrival, the day of departure and the country (or the fact that it was not indicated) for the $i$-th participant.

The sum of $n$ among all test cases in the input does not exceed $500$.

输入的第一行包含一个整数 $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$。

Output $t$ integers — maximum number of upset scientists for each test case.

输出 $t$ 个整数——每个测试用例中感到不满的科学家的最大人数。