Coloring Intervals

For real numbers $a \le b$, the closed interval $[a, b]$ is the set of all real numbers between $a$ and $b$, inclusive. For example, $[3, 5] = \{x \in \mathbb{R} \mid 3 \le x \le 5\}$.

Bob has $n$ closed intervals $[a_1, b_1], [a_2, b_2], \dots, [a_n, b_n]$. For every pair of distinct indices $i, j \in \{1, 2, \dots, n\}$, all of the following hold.

• $a_i$ and $b_i$ are positive integers.
• $a_i \le b_i$, so $[a_i, b_i]$ is not empty.
• $a_i \ne b_j$, $a_i \ne a_j$ and $b_i \ne b_j$, so two different closed intervals never share an endpoint.

Bob wants to color each interval with a single color so that any two overlapping intervals get different colors. He wants to know how many colors that takes. In other words, find the smallest positive integer $k$ such that each interval can be labelled with one of $1, 2, \dots, k$ and any two overlapping intervals always carry different labels. Two intervals overlap when their intersection is not empty.

The first line contains the number $T$ of test cases. Each of the next $T$ lines describes one test case by giving $n$, $a_1$, $b_1$, $a_2$, $b_2$, $\dots$, $a_n$, $b_n$, in that order. Two consecutive numbers on a line are separated by one or more spaces.

You may assume the following.

• $1 \le T \le 10$
• $n \in \{2, 3, \dots, 100\,000\}$
• $a_i$ and $b_i$ are positive integers no larger than $2^{32} - 1$ for every $i \in \{1, 2, \dots, n\}$.

For each test case, print the minimum number of colors $k$ on its own line. That is, print the smallest positive integer such that each of $[a_1, b_1], [a_2, b_2], \dots, [a_n, b_n]$ can be labelled with one of $1, 2, \dots, k$ and any two overlapping intervals always carry different labels.