Description

庞教授有一个多重区间集 $S=\{[l_i,r_i]\}$（$l_i<r_i$）。

庞教授将对 $|S|-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$ 中恰好包含一个区间，庞教授将得到这个区间作为礼物。

现在庞教授希望你计算他可以得到多少个不同的区间。

Input Format

第一行包含一个整数 $T$（$1\le T \le 10^4$），表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$1\le n\le 10^5$）——$S$ 的大小。接下来的 $n$ 行中的每一行包含两个整数 $l_i$ 和 $r_i$（$1\le l_i<r_i\le 10^9$），描述 $S$ 中的第 $i$ 个区间。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

Output Format

对于每个测试用例，输出一行，包含庞教授问题的答案。

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

Hint

题面翻译由 ChatGPT-4o 提供。