클리크

원을 시계 방향으로 1번부터 $10^6$번까지 번호를 붙인 $10^6$개의 호(arc)로 나눈다. 원 위에는 각각 연속된 호의 구간을 차지하는 선분 $n$개가 있다.

임의의 두 선분이 적어도 하나의 공통된 호를 공유하도록 고를 때, 그런 선분 집합의 최대 크기를 구하라.

첫 줄에 테스트 케이스의 개수 $z$가 주어진다. 각 테스트 케이스의 첫 줄에는 선분의 개수 $n$ ($1 \le n \le 3000$)이 주어진다. 이어서 $n$개의 줄에 정수 $l_i$와 $r_i$ ($1 \le l_i, r_i \le 10^6$)가 주어지며, 이는 시계 방향으로 따라갈 때 $i$번째 선분의 첫 호와 마지막 호이다. 어떤 선분도 원 전체를 차지하지 않으며, 같은 선분이 두 번 주어지지 않는다.

모든 테스트 케이스의 $n$을 합한 값은 24000을 넘지 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 정수는 모든 쌍이 서로 교차하는 선분 집합의 최대 크기이다.