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). 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. 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). 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 t