G1. The Destruction of the Universe (Easy Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. In this version, $$$n \leq 5000$$$. You can only make hacks if both versions of the problem are solved.

Orangutans are powerful beings—so powerful that they only need $$$1$$$ unit of time to destroy every vulnerable planet in the universe!

There are $$$n$$$ planets in the universe. Each planet has an interval of vulnerability $$$[l, r]$$$, during which it will be exposed to destruction by orangutans. Orangutans can also expand the interval of vulnerability of any planet by $$$1$$$ unit.

Specifically, suppose the expansion is performed on planet $$$p$$$ with interval of vulnerability $$$[l_p, r_p]$$$. Then, the resulting interval of vulnerability may be either $$$[l_p - 1, r_p]$$$ or $$$[l_p, r_p + 1]$$$.

Given a set of planets, orangutans can destroy all planets if the intervals of vulnerability of all planets in the set intersect at least one common point. Let the score of such a set denote the minimum number of expansions that must be performed.

Orangutans are interested in the sum of scores of all non-empty subsets of the planets in the universe. As the answer can be large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the number of planets in the universe.

The following $$$n$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — the initial interval of vulnerability of the $$$i$$$-th planet.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$5000$$$ over all test cases.

Output

For each test case, output an integer — the sum of scores to destroy all non-empty subsets of the planets in the universe, modulo $$$998\,244\,353$$$.

Example
Input
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
Output
5
6
24
Note

In the first testcase, there are seven non-empty subsets of planets we must consider:

  • For each of the subsets $$$\{[1,1]\}, \{[2,3]\}, \{[3,3]\}$$$, the score is $$$0$$$.
  • For the subset $$$\{[2,3], [3,3]\}$$$, the score is $$$0$$$, because the point $$$3$$$ is already contained in both planets' interval of vulnerability.
  • For the subset $$$\{[1,1], [2,3]\}$$$, the score is $$$1$$$. By using one operation on changing the interval of vulnerability of the second planet to be $$$[1,3]$$$, the two planets now both have the point $$$1$$$ in their interval.
  • For the subset $$$\{[1,1], [3,3]\}$$$, the score is $$$2$$$. By using two operations on changing the interval of vulnerability of the first planet to be $$$[1,3]$$$, the two planets now both have the point $$$3$$$ in their interval.
  • For the subset $$$\{[1,1], [2,3], [3,3]\}$$$, the score is $$$2$$$. By using one operation on changing the interval of vulnerability of the first planet to be $$$[1,2]$$$ and one operation on changing the interval of vulnerability of the third planet to $$$[2,3]$$$, all three planets will have the point $$$2$$$ in their interval.

The sum of scores of all non-empty subsets of the first testcase is $$$0 \cdot 4 + 1 \cdot 1 + 2\cdot2 = 5$$$.