Busy Beaver 是 Sheet Music Boss 的忠实粉丝，梦想着在钢琴上演奏冗长而复杂的乐曲。然而，他只有可怜的 10 根手指，能做的事情非常有限。幸运的是，他的朋友 Ditto 的手上可以长出任意数量的手指，这让他们能够演奏任何想象得到的乐曲。

Ditto 正尝试演奏一首由 $N$ 个音符组成的乐曲，音符编号为 $1$ 到 $N$。为了演奏第 $i$ 个音符，Ditto 必须在时间 $a_i$ 按下琴键 $k_i$，并在时间 $b_i$ 松开。保证不会在同一时间演奏两个使用相同琴键的音符。换句话说，对于所有满足 $k_i = k_j$ 的音符对 $(i, j)$，要么 $b_i \le a_j$，要么 $b_j \le a_i$。

Ditto 计划使用一只拥有 $F$ 根手指的手来演奏这首乐曲，手指从左到右依次编号为 $1$ 到 $F$。他们希望将手指 $f_i$ 分配给第 $i$ 个音符。如果 Ditto 能够为每个音符分配一根手指并满足以下标准，他们就可以演奏这首乐曲：

• 在任何时间点，他们的手指都不会交叉。形式化地，对于所有存在时间 $t$ 满足 $a_i < t < b_i$ 且 $a_j < t < b_j$ 的音符对 $(i, j)$，如果 $k_i < k_j$，则 $f_i < f_j$。

Ditto 被允许从乐曲中删除最多 $M$ 个音符，其中 $M$ 为 $0$ 或 $1$。求他们手上需要的最少手指数量，以便能够演奏剩余的乐曲。换句话说，求最小的 $F$，使得存在一个满足上述标准的手指分配方案 $f$。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 2 \cdot 10^5$，$M = 0$ 或 $1$)。

接下来的 $N$ 行中，第 $i$ 行包含三个整数 $k_i$、$a_i$ 和 $b_i$ ($1 \le k_i \le 10^9$，$1 \le a_i < b_i \le 10^9$) —— 表示第 $i$ 个音符在时间 $a_i$ 到 $b_i$ 期间使用琴键 $k_i$。

保证不会在同一时间演奏两个使用相同琴键的音符，且所有测试用例中 $N$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 Ditto 手上需要的最少手指数量，使得在删除最多 $M$ 个音符后，存在一个满足要求的手指分配方案。

子任务

本题共有三个子任务。

• （10 分）：所有测试用例中 $N$ 的总和不超过 $10^3$ 且 $M = 0$。
• （20 分）：$M = 0$。
• （70 分）：无附加限制。

样例

输入样例 1

5
5 0
3 3 6
5 2 5
6 5 6
1 1 4
1 5 7
5 1
2 1 6
10 1 6
4 5 9
8 5 9
6 8 10
4 1
1 1 2
2 1 2
1 3 4
2 3 4
1 0
6 2 5
1 1
6 2 5

输出样例 1

3
3
2
1
0

说明

第一个测试用例的音符如下图所示。x 轴表示按下的琴键，y 轴表示按下音符的时间区间。所需的最少手指数量为 3 —— 每个音符上都标有实现此目的的手指编号。

第二个测试用例的音符如下图所示。删除黄色或蓝色的音符都可以使 3 根手指足够，且这是最优的。