CF2030G1.The Destruction of the Universe (Easy Version)

这是问题的简单版本，满足 $ n \leq 5000 $。如果两个版本的问题都被解决，才可以进行挑战。

猩猩是强大的生物，它们只需要 $1$ 个单位时间就能摧毁宇宙中每一个脆弱的星球！

宇宙中有 $n$ 个星球。每个星球在一个区间 $[l, r]$ 内是脆弱的，期间随时可能被猩猩摧毁。猩猩可以把任意一个星球的脆弱区间扩展 $1$ 个单位。

具体来说，如果对某个星球 $p$ 的脆弱区间 $[l_p, r_p]$ 进行扩展，结果可以是 $[l_p - 1, r_p]$ 或 $[l_p, r_p + 1]$ 中的任一个。

给定一组星球，如果它们的所有脆弱区间中至少有一个共同点，那么这组星球就能被摧毁。我们把这样一组星球的“得分”定义为实现摧毁所需的最小扩展次数。

猩猩关注的是宇宙中所有非空星球子集的得分之和。由于可能结果非常大，请输出答案对 $998\,244\,353$ 取模后的结果。

第一行是一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

每个测试用例的第一行有一个整数 $n$（$1 \leq n \leq 5000$）——星球的数量。

接下来的 $n$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个星球的初始脆弱区间。

保证所有测试用例中，星球数量的总和不超过 $5000$。

对于每个测试用例，输出一个整数——所有非空星球子集的得分之和，对 $998\,244\,353$ 取模。

以第一个测试用例为例，需考虑以下七个非空子集：

• 对于子集 $\{[1,1]\}, \{[2,3]\}, \{[3,3]\}$，得分为 $0$。
• 对于子集 $\{[2,3], [3,3]\}$，得分为 $0$，因为点 $3$ 已经位于这两个星球的脆弱区间之内。
• 对于子集 $\{[1,1], [2,3]\}$，得分为 $1$。通过一次操作，将第二个星球的脆弱区间改为 $[1,3]$，这样两个星球的脆弱区间都包含点 $1$。
• 对于子集 $\{[1,1], [3,3]\}$，得分为 $2$。通过两次操作，将第一个星球的脆弱区间改为 $[1,3]$，使得两个星球的区间都包含点 $3$。
• 对于子集 $\{[1,1], [2,3], [3,3]\}$，得分为 $2$。通过一次操作把第一个星球的区间改为 $[1,2]$，再用一次操作把第三个星球的区间改为 $[2,3]$，这样三个星球都包含点 $2$。

所以，第一个测试用例中，所有非空子集的得分之和为 $0 \times 4 + 1 \times 1 + 2 \times 2 = 5$。

本翻译由 AI 自动生成