题目描述

题目译自 XX Olimpiada Informatyczna — II etap Inspektor

侦探 Bajtazar 正在调查一桩发生在程序员办公室的犯罪案件。他试图还原事件的时间线。然而，程序员们都有些心不在焉，没人能提供清晰的信息，他们只会说这样的话： 「嗯，我在 $14:42$ 登录服务器时，看到有五个其他程序员在工作。」

已知当天每个程序员来到办公室，停留一段时间后离开，且在进入和离开之间未曾离开办公室，也未在其他时间段出现在办公室。

Bajtazar 不确定能否信任这些证词。他想知道是否有可能所有证词都为真。请你协助他完成这个任务。

输入格式

第一行包含一个整数 $z$（$1 \leq z \leq 50$），表示测试数据数量。接下来的若干行描述每组测试数据。

每组测试数据的第一行包含两个整数 $n, m$（$1 \leq n, m \leq 100000$），分别表示办公室的程序员数量和 Bajtazar 收集的证词数量。程序员编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含三个整数 $t, j, i$（$1 \leq t \leq m$，$1 \leq j \leq n$，$0 \leq i < n$），表示程序员 $j$ 声称在时刻 $t$ 身处办公室，且除他之外还有 $i$ 名其他程序员。更大的 $t$ 表示更晚的时刻。假设程序员在证词涉及的时刻之前、之后或之间进入或离开办公室。

输出格式

对于每组测试数据，输出一个正整数 $k$（$1 \leq k \leq m$），表示输入中前 $k$ 个证词可能为真，而前 $k+1$ 个证词不可能同时为真。特别地，若 $k=m$，表示所有证词可能为真。

样例

输入

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

输出

4
3

解释
在第一组测试数据中，并非所有证词都能为真。程序员 $1$ 和 $2$ 声称他们至少从时刻 $1$ 到时刻 $4$ 都在办公室，而程序员 $3$ 声称在时刻 $2$ 除他之外只有一人。如果我们忽略最后一个证词，其余证词可能为真。只要程序员 $2$ 在时刻 $1$ 和 $2$ 之间离开办公室即可。

在第二组测试数据中，所有提交的证词都能为真。

附加样例

1. $z=1$, $n=5$, $m=5$，所有证词相互一致，且无程序员看到其他程序员。
2. $z=50$，每组测试数据 $n=101$, $m=101$，奇数编号测试数据的证词一致且每人看到其他人，偶数编号测试数据的不同之处在于某时刻的证词人数超过其所述人数。
3. $z=1$, $n=100000$, $m=50000$，除一个证词外其余相同，该证词与其他矛盾。

数据范围与提示

• 对于 $7\%$ 的数据，$n, m \leq 5$。
• 对于另外 $28\%$ 的数据，$n, m \leq 101$。