세기는 재미없다 (어려운 버전)

이 문제는 어려운 버전입니다. 두 버전의 차이는 이 버전에서 $t$와 $n$의 제한이 더 크다는 점입니다. 이 문제의 모든 버전을 푼 경우에만 해킹할 수 있습니다.

이제 Little John은 부자가 되어, 마침내 자신과 좋아하는 괄호 수열이 들어갈 만큼 큰 집을 샀습니다. 그런데 어쩌다 보니 괄호가 아주 많아졌습니다! 답답해진 그는 "여래신장"으로 천장을 뚫습니다.

괄호 수열이 다음 형식적인 문법으로 만들어질 수 있으면 균형 잡힌 수열이라고 합니다.

1. 빈 수열 $\varnothing$은 균형 잡힌 수열이다.
2. 균형 잡힌 수열 $A$가 있으면 $\mathtt{(}A\mathtt{)}$도 균형 잡힌 수열이다.
3. 균형 잡힌 수열 $A$와 $B$가 있으면 이어 붙인 $AB$도 균형 잡힌 수열이다.

예를 들어 "(())()", "()", "(()(()))", 빈 수열은 균형 잡힌 수열이고, "(()"와 "(()))("는 그렇지 않습니다.

균형 잡힌 괄호 수열 $s$가 주어졌을 때, 인덱스 쌍 $(i,j)$ ($i<j$)는 $s_i$가 '(', $s_j$가 ')'이고, 두 괄호가 규칙 2에 따라 $s$를 만드는 과정에서 함께 추가된 경우 좋은 쌍이라고 합니다. 예를 들어 "(())()"에는 $(1,4)$, $(2,3)$, $(5,6)$ 세 개의 서로 다른 좋은 쌍이 있습니다. 괄호 $2n$개로 이루어진 균형 잡힌 수열에는 정확히 $n$개의 서로 다른 좋은 쌍이 있으며, 같은 수열을 규칙의 적용 순서를 바꿔 만들어도 좋은 쌍의 집합은 같습니다.

Emily는 John과 괄호 맞추기 게임을 합니다. 게임은 다음과 같이 진행됩니다.

처음에 John은 서로 다른 좋은 쌍을 $n$개 가진 균형 잡힌 괄호 수열 $s$를 가지고 있으며, Emily는 이 수열을 모릅니다. John은 Emily에게 $n$의 값을 알려 주고 수열을 맞혀 보라고 합니다.

$n$번의 턴에 걸쳐 John은 매 턴마다 다음 형태의 단서를 줍니다.

• $l\,r$: 수열 $s$에 좋은 쌍 $(l,r)$이 있습니다.

John이 Emily에게 주는 단서들은 모두 서로 다르며 서로 모순되지 않습니다.

어느 시점에서는 지금까지 주어진 단서를 만족하는 균형 잡힌 수열이 하나뿐이라는 것을 Emily가 확신할 수 있습니다. 예를 들어 Emily가 $s$에 좋은 쌍이 $3$개 있다는 것을 알고 있고, 좋은 쌍 $(2,5)$가 들어 있다고 합시다. 좋은 쌍이 $3$개인 균형 잡힌 수열 $5$개 중에서 좋은 쌍 $(2,5)$를 갖는 수열은 "((()))" 하나뿐입니다. 따라서 Emily가 $s$를 알아내는 데 항상 $n$번의 턴이 필요한 것은 아닙니다.

Emily가 $s$의 내용을 가능한 한 일찍 알아내려면, 각 턴 뒤에 단서와 맞는 서로 다른 균형 잡힌 수열의 개수를 알아야 합니다. 좋은 쌍이 많으면 이 계산은 특히 어렵습니다. 이제 여러분이 Emily를 도울 차례입니다. 단서가 주어질 때마다 턴 전후의 답을 구하십시오. 답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구합니다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^4$)가 주어집니다. 이후 테스트 케이스가 차례로 주어집니다.

각 테스트 케이스의 첫 줄에는 좋은 쌍의 개수 $n$ ($2 \le n \le 3 \cdot 10^5$)이 주어집니다.

이어서 $n$개의 줄에 $i$번째 단서를 나타내는 두 정수 $l_i$와 $r_i$ ($1 \le l_i < r_i \le 2n$)가 주어집니다.

한 테스트 케이스의 단서들은 모두 서로 다르며 서로 모순되지 않습니다.

모든 테스트 케이스에 대한 $n$의 합은 $3 \cdot 10^5$를 넘지 않습니다.

각 테스트 케이스마다 $n+1$개의 정수를 한 줄에 출력합니다.

• 첫 번째 정수는 단서를 하나도 주지 않았을 때의 답입니다.
• $i \ge 1$인 모든 $i$에 대해, $i+1$번째 정수는 $i$번째 단서를 준 뒤의 답입니다.

예제의 첫 번째 테스트 케이스는 문제 설명에서 이미 다루었습니다.

예제의 세 번째 테스트 케이스는 다음과 같이 설명됩니다. 좋은 쌍이 $6$개인 균형 잡힌 수열은 $132$개입니다. 각 단서를 준 뒤의 답은 다음과 같습니다.

1. 좋은 쌍 $(2,3)$을 주었습니다. 좋은 쌍 $(2,3)$을 갖는 균형 잡힌 수열은 $42$개입니다.
2. 좋은 쌍 $(1,6)$을 주었습니다. 좋은 쌍 $(2,3)$과 $(1,6)$을 갖는 수열은 $5$개입니다.
3. 좋은 쌍 $(7,8)$을 주었습니다. 좋은 쌍 세 개를 모두 갖는 수열은 $2$개이며, 그 수열은 각각 "(()())()(())"와 "(()())()()()"입니다.
4. 좋은 쌍 $(9,12)$를 주었습니다. 좋은 쌍 네 개를 모두 갖는 수열은 하나뿐입니다. 따라서 $s$는 "(()())()(())"로 정해집니다.