검사관

검사관 바이트아사르(Byteasar)는 어느 소프트웨어 회사에서 일어난 사건을 수사하며 사건의 전개 과정을 재구성하려 한다. 그런데 프로그래머들은 하나같이 덤벙대는 편이라, 그들에게서 얻을 수 있는 가장 쓸모 있는 정보라고 해봐야 "14시 42분에 시계를 봤을 때, 서버에는 저 말고 다른 프로그래머 다섯 명이 접속해 있었어요." 같은 진술이 전부다.

프로그래머는 각자 그날 하루 중 한 번 사무실에 와서, 중간에 나가는 일 없이 연속된 시간 동안 머문 뒤, 완전히 퇴근하며 그날은 다시 돌아오지 않는다.

바이트아사르는 이 진술들을 얼마나 믿어야 할지 확신이 서지 않는다. 그는 우선 이 진술들이 모두 동시에 참일 수 있는지부터 알고 싶다. 그가 판단할 수 있도록 도와주자.

첫째 줄에 테스트 케이스의 수 $z$ ($1 \le z \le 50$)가 주어진다. 이어서 $z$개의 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 100\,000$)이 주어진다. 각각 사무실에서 일하는 프로그래머의 수와 바이트아사르가 기록한 진술의 수이다. 프로그래머는 $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$개는 그럴 수 없다. 만약 $m$개의 진술이 모두 동시에 참일 수 있다면 $m$을 출력한다.

첫 번째 예제에서는 처음 네 진술까지는 동시에 성립할 수 있지만, 다섯 번째 진술을 더하면 모순이 생긴다. 그 경우 프로그래머 $1$번과 $2$번이 모두 시각 $1$부터 시각 $4$까지 사무실에 있어야 하므로, 시각 $2$에는 사무실에 적어도 세 명($1$번, $2$번, $3$번)이 있게 된다. 이는 시각 $2$에 자기 말고 다른 프로그래머가 한 명뿐이었다는 프로그래머 $3$번의 진술과 어긋난다. 따라서 답은 $4$이다.

두 번째 예제에서는 세 진술이 서로 모순되지 않으므로 답은 $3$이다.