책 나눠주기

지호는 방을 정리하다가 이제 필요 없는 전공 서적을 다른 사람에게 나눠주기로 했다. 나눠줄 책은 모두 $N$권이고, 책을 구분하려고 $1$번부터 $N$번까지 서로 다른 번호를 붙여 두었다.

책을 받고 싶다고 신청한 서강대학교 학부생은 모두 $M$명이다. 지호는 학생마다 신청서에 두 정수 $a$, $b$ ($1 \le a \le b \le N$)를 적어 내게 했다. 지호는 번호가 $a$ 이상 $b$ 이하인 책 중에서 아직 남아 있는 한 권을 골라 그 학생에게 준다. $a$번부터 $b$번까지의 책이 이미 모두 다른 학생에게 갔다면 그 학생은 책을 받지 못한다.

지호는 신청서를 처리하는 순서와 매번 고르는 책을 마음대로 정할 수 있다. 책을 받는 학생 수를 최대로 만들었을 때, 그 학생 수를 구하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에 정수 $N$ ($1 \le N \le 1000$)과 $M$ ($1 \le M \le 1000$)이 공백을 두고 주어진다. 이어지는 $M$개의 줄에는 신청서에 적힌 두 정수 $a_i$, $b_i$ ($1 \le a_i \le b_i \le N$)가 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 책을 받는 학생 수의 최댓값을 한 줄에 하나씩 출력한다.