No submission language available for this problem.

Background

Special for beginners, ^_^

Description

现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。

门口路边的地区被分割成块，并被编号成 1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码 B，E，T。这三个数表示该居民想在 B 和 E 之间最少种 T 棵树。当然，B ≤ E，居民必须记住在指定区不能种多于区域地块数的树，所以 T ≤ E - B + 1。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量较少政府的支出。

Format

Input

第一行一个整数 T， 表示有 T 组测试

每组测试第一行包含数据 N，M，区域的个数(0 < N ≤ 30000)，房子的数目 (0 < m ≤ 5000)；

之后的 m 行描述居民们的需要：B E T，0 < B ≤ E ≤ 30000，T ≤ E-B+1。

Output

输出一个数，为满足所有居民的要求，所需要种树的最少数量。

Samples

1
9 4
3 5 2
1 4 2
4 6 2
8 9 2

5

Limitation

1s, 1024KiB for each test case.