Prof. Pang 有一个区间多重集 $S = \{[l_i, r_i]\}$ ($l_i < r_i$)。 Prof. Pang 将执行 $|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$ 中恰好包含一个区间，Prof. Pang 将得到这个区间作为礼物。 现在 Prof. Pang 想让你计算他能得到的不同区间有多少个。

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一行，包含 Prof. Pang 问题的答案。

样例

输入 1

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

1
499999999500000000
26
28