给你一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$ 和 $m$ 个修改操作。第 $i$ 次操作由三个参数 $l_i, r_i, c_i$ 描述，表示你可以选择将子数组 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ 中的所有元素设置为 $c_i$。对于每个操作，你可以选择执行它或跳过它。

你的目标是通过最优地决定是否执行每个操作（按给定的顺序处理），来最大化最终数组中连续段的数量。连续段的数量定义为 $1 + \sum_{i=2}^n [a_i \neq a_{i-1}]$，即相邻不同元素的数量加一。

此外，所有操作都满足以下特殊性质：对于任意两个操作 $i < j$，区间 $[l_j, r_j]$ 不是 $[l_i, r_i]$ 的子区间。换句话说，不存在 $i < j$ 使得 $l_i \le l_j$ 且 $r_j \le r_i$ 同时成立。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T (1 \le T \le 10000)$，表示测试用例的数量。

每个测试用例由以下部分组成：

• 第一行包含两个正整数 $n (1 \le n \le 3 \times 10^5)$ 和 $m (1 \le m \le 3 \times 10^5)$，分别表示数组的长度和操作的数量。
• 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n (1 \le a_i \le n)$，表示初始数组。
• 接下来的 $m$ 行，每行包含三个整数 $l_k, r_k, c_k$，描述第 $k$ 个操作（$1 \le l_k \le r_k \le n$，$1 \le c_k \le n$）。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$，且 $m$ 的总和不超过 $3 \times 10^5$。

输出格式

输出一个整数，表示在最优地执行操作后，最终数组中能达到的最大连续段数量。

样例

输入样例 1

2
5 5
1 1 1 1 1
1 2 3
2 3 4
1 3 4
2 4 4
5 5 3
3 1
1 1 1
2 2 2

输出样例 1

4
3