You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

‎TT和FF是...朋友。呃。。。非常非常好的朋友 -________‎

‎FF是个坏小子，他总是在拉拢TT和他一起玩下面的游戏。这是一个非常单调的游戏。首先，TT 应该记下一个整数序列-_-!!（无聊）。‎

‎然后，FF 可以从中选择一个连续的子序列（例如，从第三个整数到第五个整数的子序列（包括第三个整数）。子序列）。之后，FF会问TT他选择的子序列的总和是多少。接下来，TT将回答FF的问题。然后，FF 可以重做此过程。最后，FF 必须计算出整数的整个序列。‎

‎无聊‎‎无聊 无聊‎‎一个非常非常无聊的游戏!!!TT根本不想和FF一起玩。为了惩罚FF，她经常故意告诉FF错误的答案。‎

‎坏男孩不是傻瓜。FF发现有些答案不相容。当然，这些矛盾使得计算序列变得困难。‎

‎然而，TT是一个漂亮可爱的女孩。她没有心思对FF苛刻。为了节省时间，她保证，如果确实没有逻辑错误，答案是正确的。‎

‎更重要的是，如果FF发现一个错误的答案，他在判断下一个答案时会忽略它。‎

‎但是会有太多的问题，可怜的FF无法确定当前的答案是正确还是错误。所以他决定写一个程序来帮助他解决这个问题。该计划将收到FF的一系列问题以及FF从TT收到的答案。该程序的目的是找出有多少答案是错误的。只有忽略错误的答案，FF才能计算出整数的整个序列。可怜的FF没有时间做这项工作。而现在他正在向你求助~（为什么要给自己找麻烦~~坏小子）‎

Format

Input

开始输入一个整数T，表示有T组数据，T后的第一行为，下文描述的第一行

‎第 1 行：两个整数，N 和 M（1 <= N < = 1000000，1 < = M < = 1000000）。意味着TT写了N个整数，FF问了她M个问题。‎

‎第 2 行...M+1：i+1行包含三个整数：Ai、Bi 和 Si，表示 TT 回答了 FF，即从 Ai 到 Bi 的总和是 Si。保证 0 < Ai <= Bi <= N。‎

‎您可以假定子序列的任何总和都适合 32 位整数。‎

Output

‎带有整数的单行表示有多少答案是错误的。‎

Samples

1
10 5
1 10 100
7 10 28
1 3 32
4 6 41
6 6 1

1

Limitation

1s, 1024KiB for each test case.