Description

Inspector Byteasar is investigating a crime that took place on the premises of a software development company. He is trying to establish the chain of events. Unfortunately, the programmers are rather scatterbrained. Statements of the kind "Well, when I checked at 14:42, there were five other programmers logged in on the server." are the most informative of those that Byteasar could get.

It is known that every programmer came to office at some point during that day, spent some time in there without going out, and then left for good, never coming back on the same day.

Byteasar, confused by the programmers' statements, is not sure if he should rely on them. In fact, he is wondering whether it is at all possible that they all tell the truth. He asks you for help in finding that out.

一天公司有n个员工和m个员工记录，每个员工只会在连续的一段时间内工作。当然写观察记录的时候肯定会在工作。记录会给出当时除了他还有多少人在公司。现在给出m条记录分别是谁写的、什么时候写的以及写的时候还有多少人。求第k条记录使得前k条记录可以同时存在不矛盾，且前k+1条记录是矛盾的。输出这个k。

Format

Input

In the first line of the standard input, there is an integer Z (1<=Z<=50) , the number of data sets. The lines that follow contain the Z data sets.

The first line of each data set holds two integers, N and M , separated by a single space(1<=N,M<=100000) . These are 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 m lines that follow describes a single statement. Each such line contains three integers , , and , separated by single spaces 1<=T<=M,1<=j<=N 0<=i<=N

These indicate that the programmer no. confessed that at time he was in the office and there were more programmers apart from him. We assume that the programmers came in to the office and left it at times different from those appearing in the statements, i.e., either before, after or in between them.

Output

For each data set, your program should print a single positive integer to the standard output. Printing out the number K(1<=K<=M) indicates that the first statements given on the input can be true but the first K+1 statements cannot. In particular, if K=M, then all the statements given as input can be true.

Samples

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

Limitation

Explanation of the example: In the first data set, the statements given by programmers cannot all be true. The programmers 1 and 2 stated that they were in the office between times 1 and 4 but the programmer 3 stated that at time 2 there was only a single person apart from him there. If we discount that last statement, the remaining ones can be true.