Menji likes watching table tennis matches, but because there are so many spectators, he can only hear part of the information.

A table tennis match consists of $T$ games. The process of a single game is as follows:

Two players have scores, denoted by $s_A$ and $s_B$, initially $s_A = s_B = 0$.

Several rallies are played. In the $i$-th rally, there is a winner $win_i (win_i \in \{\texttt{A}, \texttt{B}\})$. If $win_i = \texttt{A}$, then $A$'s score increases by $1$, i.e., $s_A = s_A + 1$; otherwise, $B$'s score increases by $1$, i.e., $s_B = s_B + 1$. When either player reaches $11$ points and leads the other player by at least $2$ points (i.e., $\max(s_A, s_B) \geq 11$ and $\max(s_A, s_B) - \min(s_A, s_B) \geq 2$), the game ends immediately.

For each game, Menji hears the total number of rallies $n$ played in that game, as well as the score at the end of some rallies. For example, Menji might hear that the score at the end of the $5$-th rally is $3:2$, but Menji does not know which player scored $3$ points; he only knows that one player scored $3$ points and the other scored $2$ points.

Specifically, Menji's information can be represented as a non-negative integer $n$, indicating that the game lasted exactly $n$ rallies, and two sequences of length $n$, $a_1 \cdots a_n$ and $b_1 \cdots b_n$. For each $i (1 \leq i \leq n)$, if $a_i = b_i = -1$, Menji did not hear any information about the score at the end of the $i$-th rally. Otherwise, it is guaranteed that $0 \leq a_i, b_i \leq n$, meaning that at the end of the $i$-th rally, it must be true that either $s_A = a_i, s_B = b_i$ or $s_A = b_i, s_B = a_i$.

Obviously, in many cases, Menji's information is not enough to reconstruct the winner of every rally in the game, and sometimes Menji's information might even be incorrect. Menji wants to know how many winner sequences $win_1 \cdots win_n$ satisfy all the information he knows.

Since the answer can be very large, please output the answer modulo $998244353$.

Input

The input is read from standard input.

The first line contains an integer $T (1 \leq T \leq 10^5)$, representing the number of table tennis games.

For each game:

The first line contains an integer $n$, representing that the game lasted exactly $n (1 \leq n \leq 10^5)$ rallies.

The following $n$ lines each contain two integers $a_i, b_i$, satisfying $a_i = b_i = -1$ or $0 \leq a_i, b_i \leq n$, representing the partial information Menji knows.

It is guaranteed that the total number of rallies does not exceed $5 \times 10^5$, i.e., $\sum n \leq 5 \times 10^5$.

Output

Output to standard output.

For each game, output one line containing a single number representing the number of possible winner sequences, modulo $998244353$.

Examples

Input 1

7
11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11
-1 -1
1 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 11
22
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11 9
-1 -1
-1 -1
22
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
23
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
22
-1 -1
1 1
-1 -1
3 1
-1 -1
4 2
-1 -1
2 6
-1 -1
-1 -1
5 6
-1 -1
-1 -1
7 7
-1 -1
-1 -1
9 8
-1 -1
9 10
-1 -1
11 10
-1 -1

Output 1

2
0
0
0
369512
0
864

Note

The match consisted of $7$ games in total.

• For the first game, it ended after exactly $11$ rallies; one player must have won $11$ consecutive rallies, so the winner sequence must be all $\texttt{A}$ or all $\texttt{B}$, so the answer is $2$.
• For the second game, it ended after exactly $11$ rallies, but the score at the end of the second rally was $1:1$, and the maximum score possible at the end is $10:1$, so no valid winner sequence exists that ends at exactly $11$ rallies, so the answer is $0$.
• For the third game, it is obviously impossible to reach a score of $1:11$ within $11$ rallies, so the answer is $0$.
• For the fourth game, if the score reached $11:9$ at the $20$-th rally, the game would have ended immediately and would not have continued to the $22$-nd rally, so the answer is $0$.
• For the fifth game, the scores must have reached $10:10$ first, after which one player won $2$ consecutive rallies, so the answer is $\binom{20}{10} \times 2 = 369512$.
• For the sixth game, it is easy to see that it is impossible to end at exactly $23$ rallies, so the answer is $0$.
• For the seventh game, I have a perfect explanation, but unfortunately, there is no room to write it down.