This is the hard version of the problem. In this version, $n \leq 10^6$. 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 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^6$) — 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 $10^6$ 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$.

见题面 Input 部分

见题面 Output 部分

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$.