Byteasar 探长正在调查一起发生在某软件开发公司的案件。他试图还原事件的经过。不幸的是，程序员们都有些健忘。Byteasar 能得到的最有价值的信息是类似“嗯，我在 14:42 查看时，服务器上还有其他五名程序员登录”这样的陈述。

已知每位程序员在当天某个时刻来到办公室，在里面待了一段时间后离开，且当天不再返回。

Byteasar 对程序员们的陈述感到困惑，他不确定是否应该相信他们。事实上，他想知道这些陈述是否有可能全部属实。他请求你帮助他查明这一点。

输入格式

标准输入的第一行包含一个整数 $z$ ($1 \le z \le 50$)，表示数据组数。接下来的行包含 $z$ 组数据。

每组数据的第一行包含两个整数 $n$ 和 $m$，由空格分隔 ($1 \le n, m \le 100\,000$)。它们分别表示办公室里的程序员人数和 Byteasar 记录的陈述条数。程序员编号为 $1$ 到 $n$。

接下来的 $m$ 行，每行描述一条陈述。每行包含三个整数 $t$、$j$ 和 $i$，由空格分隔 ($1 \le t \le m$，$1 \le j \le n$，$0 \le i \le n$)。这表示编号为 $j$ 的程序员承认在时间 $t$ 他在办公室，且除他之外还有 $i$ 名程序员在场。我们假设程序员进入和离开办公室的时间与陈述中出现的时间点不同，即要么在这些时间点之前、之后，要么在它们之间。

输出格式

对于每组数据，你的程序应向标准输出打印一个正整数。打印数字 $k$ ($1 \le k \le m$) 表示输入的前 $k$ 条陈述可能同时为真，但前 $k+1$ 条陈述不能同时为真。特别地，如果 $k=m$，则说明输入的所有陈述都可以同时为真。

样例

输入 1

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

输出 1

4
3

说明

在第一组数据中，程序员们的陈述不能全部为真。程序员 1 和 2 声称他们在时间 1 到 4 之间在办公室，但程序员 3 声称在时间 2 时，除他之外只有一个人在场。如果我们忽略最后一条陈述，其余的陈述是可以同时为真的。