题目描述

Prof. Pang has a multi-set of intervals $S=\{[l_i,r_i]\}$($l_i<r_i$).

Prof. Pang will perform the following operation for $|S|-1$ times:

• Select two intervals $[a,b]$ and $[c,d]$ from $S$, and then choose two integers $x,y$ satisfying $x\in [a,b], y\in [c,d], x<y$. After that, delete $[a,b]$ and $[c,d]$ from $S$, and add $[x,y]$ to $S$.

It's easy to find that $S$ contains exactly one interval after the operations, and Prof. Pang will get the interval as a gift.

Now Prof. Pang wants you to calculate how many different intervals he can get.

输入格式

The first line contains one integer $T~$($1\le T \le 10^4$), the number of test cases.

For each test case, the first line contains one integer $n~$($1\le n\le 10^5$) --- the size of $S$. Each of the following $n$ lines contains two integers $l_i$ and $r_i~$($1\le l_i<r_i\le 10^9$), describing the $i$-th interval in $S$.

It is guaranteed that the sum of $n$ over all test cases is no more than $10^5$.

输出格式

For each test case, output one line containing the answer to Prof. Pang's question.

题目大意

蓝蓝有一个元素全为闭区间的可重集 $S=\{[l_i,r_i]\}$($l_i<r_i$)。

蓝蓝将会执行以下操作 $n-1$ 次：

• 从 $S$ 内选择两个闭区间 $[a,b]$ 和 $[c,d]$，再选择两个整数 $x,y$ 满足 $x\in [a,b], y\in [c,d], x<y$，然后从 $S$ 中删去 $[a,b]$ 和 $[c,d]$，并把 $[x,y]$ 添加进 $S$。

显然最终 $S$ 中有且仅有一个区间。现在蓝蓝想知道她可以获得多少不同的区间。

4
1
1 1000000000
2
1 1000000000
1 1000000000
4
1 2
3 4
5 6
7 8
4
1 3
2 4
5 8
6 7

1
499999999500000000
26
28