세는 것은 재미없다 (쉬운 버전)

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

이제 리틀 존은 부자가 되어, 마침내 자신과 가장 좋아하는 괄호 문자열이 들어갈 만큼 큰 집을 샀다. 그런데 어쩌다 보니 괄호가 아주 많아졌다. 답답해진 그는 "부처의 손바닥"으로 천장을 뚫고 지나간다.

다음 문법으로 만들 수 있는 괄호 문자열을 올바른 괄호 문자열이라고 한다.

1. 빈 문자열 $\varnothing$은 올바른 괄호 문자열이다.
2. 올바른 괄호 문자열 $A$가 있으면 $\mathtt{(}A\mathtt{)}$도 올바른 괄호 문자열이다.
3. 올바른 괄호 문자열 $A$, $B$가 있으면 이어 붙인 $AB$도 올바른 괄호 문자열이다.

예를 들어 "(())()", "()", "(()(()))", 빈 문자열은 올바른 괄호 문자열이고, "(()"와 "(()))("는 아니다.

올바른 괄호 문자열 $s$가 주어졌을 때, $i<j$인 인덱스 쌍 $(i,j)$가 $s_i$는 '(', $s_j$는 ')'이고, $s$를 만들 때 2번 규칙으로 두 괄호가 함께 추가되었다면 이를 좋은 쌍이라고 한다. 예를 들어 "(())()"에는 좋은 쌍이 $(1,4)$, $(2,3)$, $(5,6)$ 세 개 있다. $2n$개의 괄호로 이루어진 올바른 괄호 문자열에는 정확히 $n$개의 좋은 쌍이 있으며, 같은 문자열을 만들 때 규칙을 어떤 순서로 적용하든 좋은 쌍의 집합은 같다.

에밀리는 존과 괄호 추측 게임을 한다. 존에게는 좋은 쌍이 $n$개인 올바른 괄호 문자열 $s$가 있고, 에밀리는 이를 모른다. 존은 $n$의 값을 알려 주고 에밀리에게 $s$를 맞혀 보라고 한다. 존은 $n$번의 턴 동안 매 턴마다 다음 형태의 단서를 준다.

• $l\,r$: 문자열 $s$에 좋은 쌍 $(l,r)$이 있다.

단서들은 서로 다르며 서로 모순되지 않는다.

어느 시점에 이르면, 지금까지의 단서를 만족하는 올바른 괄호 문자열이 하나뿐이라고 에밀리가 확신할 수 있다. 예를 들어 에밀리가 $s$의 좋은 쌍이 $3$개이고 $(2,5)$를 포함한다는 것을 안다고 하자. 좋은 쌍이 $3$개인 올바른 괄호 문자열 $5$개 중 $(2,5)$를 포함하는 것은 "((()))" 하나뿐이므로, 에밀리는 $n$번의 턴을 모두 쓰지 않아도 된다.

에밀리는 매 턴 후에 지금까지의 단서에 맞는 올바른 괄호 문자열이 몇 개인지 알고 싶어 한다. 좋은 쌍이 많으면 이 개수를 세기가 어렵다. 각 턴 전후의 개수를 $998\,244\,353$으로 나눈 나머지로 구하라.

각 테스트는 여러 개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수 $t$($1 \le t \le 10^3$)가 주어진다. 각 테스트 케이스의 첫 줄에는 좋은 쌍의 수 $n$($2 \le n \le 5000$)이 주어진다. 이어서 $n$개의 줄에 각각 $i$번째 단서를 나타내는 두 정수 $l_i$와 $r_i$($1 \le l_i < r_i \le 2n$)가 주어진다.

한 테스트 케이스의 단서들은 서로 다르며 모순되지 않는다. 모든 테스트 케이스의 $n$ 합은 $5000$을 넘지 않는다.

각 테스트 케이스마다 한 줄에 $n+1$개의 정수를 출력한다. 첫 번째 정수는 단서를 하나도 주기 전의 개수이다. $i \ge 1$인 경우, $(i+1)$번째 정수는 $i$번째 단서를 준 뒤의 개수이다. 모든 값은 $998\,244\,353$으로 나눈 나머지이다.

샘플의 첫 번째 테스트 케이스는 문제 설명에서 다루었다. 세 번째 테스트 케이스는 다음과 같이 설명된다. 좋은 쌍이 $6$개인 올바른 괄호 문자열은 $132$개이다. 첫 번째 단서 $(2,3)$ 뒤에는 이 좋은 쌍을 가진 문자열이 $42$개이다. 두 번째 단서 $(1,6)$ 뒤에는 좋은 쌍 $(2,3)$, $(1,6)$을 가진 문자열이 $5$개이다. 세 번째 단서 $(7,8)$ 뒤에는 좋은 쌍 세 개를 가진 문자열이 "(()())()(())"와 "(()())()()()" 두 개이다. 네 번째 단서 $(9,12)$ 뒤에는 좋은 쌍 네 개를 가진 문자열이 "(()())()(())" 하나뿐이다. $s$의 내용이 이미 정해졌으므로 다섯 번째와 여섯 번째 단서 뒤의 개수는 모두 $1$이다.