题目描述

星港的观测阵列正在校准一片星域。第 $i$ 颗星球在坐标轴上有一个稳定观测窗口 $[l_i,r_i]$，只要最终选定的汇聚坐标落在这个窗口内，这颗星球就能被阵列稳定捕获。

你可以对任意一颗星球的观测窗口进行扩展。一次操作可以将某个窗口的左端点减小 $1$，或将右端点增大 $1$。

对于一组非空星球集合，如果经过若干次扩展后，这组星球的观测窗口至少有一个公共整数坐标，则称这组星球可以汇聚。该集合的得分定义为：使它可以汇聚所需的最少扩展次数。

星港想知道所有非空星球子集的得分之和。由于答案可能很大，请输出它对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含一个整数 $n$，表示星球数量。

接下来 $n$ 行，每行包含两个整数 $l_i,r_i$，表示第 $i$ 颗星球的初始观测窗口。

输出格式

对于每组测试数据，输出一行一个整数，表示所有非空星球子集的得分之和，对 $998244353$ 取模。

样例

输入

3
3
1 1
2 3
3 3
4
1 4
2 3
2 4
1 1
5
1 2
2 3
3 4
4 5
1 5

输出

5
6
24

样例解释

对于第一组测试数据，需要考虑七个非空子集：

• 子集 $\{[1,1]\}$、$\{[2,3]\}$、$\{[3,3]\}$ 的得分均为 $0$。
• 子集 $\{[2,3],[3,3]\}$ 的得分为 $0$，因为两个窗口已经有公共坐标 $3$。
• 子集 $\{[1,1],[2,3]\}$ 的得分为 $1$，可以将第二个窗口向左扩展到 $[1,3]$。
• 子集 $\{[1,1],[3,3]\}$ 的得分为 $2$，可以将第一个窗口向右扩展到 $[1,3]$。
• 子集 $\{[1,1],[2,3],[3,3]\}$ 的得分为 $2$，可以让三个窗口都包含坐标 $2$。

所以第一组答案为 $0\times 4+1\times 1+2\times 2=5$。

数据范围

对于所有测试数据，满足：

• $1\le T\le 10^4$；
• $1\le n\le 10^6$；
• $1\le l_i\le r_i\le n$；
• 所有测试数据中，$n$ 的总和不超过 $10^6$。

子任务

限制

时间限制：$1\text{s}$。

空间限制：$512\text{MB}$。