비행기 주차장

Jack은 비행기를 위한 주차장 사업을 시작했다. 넓지만 매우 좁고 긴 땅을 사들였기 때문에, 비행기는 오직 후입선출(LIFO) 순서로만 들어오고 나갈 수 있다. 즉 주차장은 스택처럼 동작한다(아래 그림 참고). 뒤쪽에 있는 비행기를 먼저 빼내어 다른 비행기를 움직일 수 있는 방법은 없으며, 가장 나중에 들어온 비행기가 항상 가장 먼저 나가야 한다.

이 제약 때문에 모든 주차 요청을 받아들이는 것이 항상 가능하지는 않다. 각 요청은 도착 예정 시각과 출발 예정 시각으로 이루어진다. 아래는 비행기 4대의 요청 표이다.

이 경우 비행기 1, 2, 4를 함께 받아들일 수 있지만, 비행기 2와 3을 동시에 받아들일 수는 없다.

서로 다른 비행기의 도착 시각이나 출발 시각이 같을 수도 있다. Jack의 승무원들은 매우 유능해서, 주차가 가능한 순서가 존재한다면 반드시 그 순서를 찾아낸다. 다른 예를 보자.

비행기 5와 6이 같은 시각에 도착하지만, 승무원들은 비행기 5가 6보다 먼저 나가야 함을 알기에 비행기 6을 먼저 넣고 그 위에 비행기 5를 넣는다.

주차 요청 목록이 주어질 때, 비행기가 후입선출 순서로만 출발할 수 있다는 조건 아래 주차할 수 있는 비행기의 최대 개수를 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다($1 \le T \le 5$). 각 테스트 케이스의 형식은 다음과 같다.

첫째 줄에 비행기의 수 $N$이 주어진다($1 \le N \le 300$). 이어지는 $N$개의 줄 중 $i$번째 줄에는 비행기 $i$의 도착 예정 시각 $S_i$와 출발 예정 시각 $T_i$가 주어진다($0 \le S_i < T_i \le 10^9$).

각 테스트 케이스마다 주차할 수 있는 비행기의 최대 개수를 정수 하나로 한 줄에 출력한다.