Inspector

Inspector Byteasar is investigating a crime that happened at a software company, and he is trying to reconstruct the chain of events. The programmers, unfortunately, are quite absent-minded. The most useful things he can get from them are statements such as: "When I glanced at the clock at 14:42, there were five other programmers besides me logged in on the server."

Each programmer came to the office once during that day, stayed for one continuous stretch of time without ever stepping out, and then left for good, never returning the same day.

Baffled by the statements, Byteasar is not even sure they can all be trusted. Before anything else he wants to know whether it is at all possible that every statement is true at the same time. Help him find out.

The first line contains an integer $z$ ($1 \le z \le 50$), the number of test cases. The test cases follow one after another.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 100\,000$): the number of programmers working in the office and the number of statements recorded by Byteasar. The programmers are numbered from $1$ to $n$.

Each of the next $m$ lines describes one statement with three integers $t$, $j$ and $i$ ($1 \le t \le m$, $1 \le j \le n$, $0 \le i \le n$): programmer $j$ claims that at moment $t$ he was in the office and that, apart from himself, exactly $i$ other programmers were there. Every programmer's arrival and departure happen at moments different from all the moments mentioned in the statements (that is, strictly before, after, or between them).

For each test case print a single line with one positive integer $k$ ($1 \le k \le m$): the largest number of leading statements that can all be true at once. In other words, the first $k$ statements can hold simultaneously, but the first $k+1$ cannot. If all $m$ statements can be true together, print $m$.

In the first example, the first four statements can hold at the same time, but adding the fifth one makes them contradictory: programmers $1$ and $2$ would then both have to be present from moment $1$ through moment $4$, so at moment $2$ there would be at least three programmers in the office (numbers $1$, $2$ and $3$). That contradicts programmer $3$, who says only one other programmer was with him at moment $2$. Hence the answer is $4$.

In the second example all three statements are mutually consistent, so the answer is $3$.