Problem Description

Given $n$ closed intervals $[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]$. Find the maximum number of intervals that can be selected such that all intersecting$^{\bm{\dagger}}$ intervals among the selected ones share a common endpoint$^{\bm{\ddagger}}$.

$\bm\dagger$ Two closed intervals $[l_1,r_1],[l_2,r_2]$ are said to intersect if and only if $l_2 \le r_1$ and $l_1 \le r_2$.
$\bm\ddagger$ Two closed intervals $[l_1,r_1],[l_2,r_2]$ are said to share a common endpoint if and only if $l_1=l_2$, $l_1=r_2$, $r_1=l_2$, or $r_1=r_2$.

Input Format

This problem contains multiple test cases.

The first line of the input contains a positive integer $T$, indicating the number of test cases.

Then, the $T$ test cases follow sequentially. For each test case:

• The first line contains a positive integer $n$.
• The next $n$ lines each contain two positive integers $l_i,r_i$.

Output Format

For each test case, output a single line containing a non-negative integer, representing the maximum number of intervals that can be selected.

4
3
1 3
2 2
1 1
5
1 3
2 3
4 5
3 5
1 4
8
1 4
2 4
3 4
1 2
2 3
1 3
3 5
4 5
16
1 4
2 4
3 4
1 2
2 3
1 3
3 5
4 5
5 8
6 8
7 8
5 6
6 7
5 7
7 9
8 9

2
4
6
12

Hint

Explanation for Sample #1

For the first test case, we can select 2 intervals: $[1,1]$ and $[1,3]$. It can be proven that there is no way to select more intervals.

For the second test case, we can select 4 intervals: $[1,3], [2,3], [4,5]$, and $[3,5]$. It can be proven that there is no way to select more intervals.

Data Range

This problem uses bundled subtasks.

For all test cases, it is guaranteed that $1 \le T \le 5$, $1 \le n \le 1\,000$, and $1 \le l_i \le r_i \le 2n$.

::cute-table{tuack}

• Special Property A: Any two given intervals do not share a common endpoint.
• Special Property B: Any two given intervals intersect.