구간 색칠하기

실수 $a \le b$에 대해 닫힌구간 $[a, b]$는 $a$ 이상 $b$ 이하인 모든 실수의 집합이다. 예를 들어 $[3, 5] = \{x \in \mathbb{R} \mid 3 \le x \le 5\}$이다.

밥에게는 닫힌구간 $n$개 $[a_1, b_1], [a_2, b_2], \dots, [a_n, b_n]$이 있다. 서로 다른 두 첨자 $i, j \in \{1, 2, \dots, n\}$에 대해 다음이 항상 성립한다.

• $a_i$와 $b_i$는 양의 정수이다.
• $a_i \le b_i$이다. 즉 $[a_i, b_i]$는 공집합이 아니다.
• $a_i \ne b_j$이고 $a_i \ne a_j$이며 $b_i \ne b_j$이다. 즉 서로 다른 두 닫힌구간은 끝점을 공유하지 않는다.

밥은 각 구간을 한 가지 색으로 칠하되, 서로 겹치는 두 구간은 반드시 다른 색으로 칠하려 한다. 이때 필요한 색의 최소 개수가 궁금하다. 다시 말해 각 구간에 $1, 2, \dots, k$ 중 하나를 붙여서 겹치는 두 구간이 언제나 서로 다른 번호를 받도록 만들 수 있는 가장 작은 양의 정수 $k$를 구하면 된다. 두 구간이 겹친다는 것은 두 집합의 교집합이 공집합이 아니라는 뜻이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각 테스트 케이스가 $n$, $a_1$, $b_1$, $a_2$, $b_2$, $\dots$, $a_n$, $b_n$ 순서로 주어진다. 한 줄 안에서 이웃한 두 수는 하나 이상의 공백으로 구분된다.

다음을 가정해도 된다.

• $1 \le T \le 10$
• $n \in \{2, 3, \dots, 100\,000\}$
• 모든 $i \in \{1, 2, \dots, n\}$에 대해 $a_i$와 $b_i$는 $2^{32} - 1$ 이하의 양의 정수이다.

각 테스트 케이스마다 최소 색 개수 $k$를 한 줄에 하나씩 출력한다. 즉 $[a_1, b_1], [a_2, b_2], \dots, [a_n, b_n]$의 각 구간에 $1$부터 $k$까지의 번호 중 하나를 붙여서 겹치는 두 구간이 언제나 서로 다른 번호를 받도록 만들 수 있는 가장 작은 양의 정수를 출력한다.