Shrek 想要在一个 $n \times n$ 的棋盘上放置 $n$ 个车，使得满足以下条件：

• 每一行和每一列恰好有 1 个车；
• 任意两个车之间的曼哈顿距离不超过 $n$。

更糟糕的是，Donkey 已经放置了一些车（幸运的是，每一行和每一列仍然最多包含一个车）。请找出放置剩余车的方案数，使得上述条件成立。由于方案数可能很大，请输出其对 $998244353$ 取模的结果。

在此，位于第 $x_1$ 行第 $y_1$ 列的车与位于第 $x_2$ 行第 $y_2$ 列的车之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ —— 测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ —— 棋盘的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。如果 $a_i = -1$，表示第 $i$ 行还没有车。否则，表示在第 $i$ 行第 $a_i$ 列有一个车。

数据范围

$1 \le t \le 10^5$ $2 \le n \le 2 \cdot 10^5$ 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 对于所有 $1 \le i \le n$，$a_i = -1$ 或 $1 \le a_i \le n$ 若 $i \neq j$ 且 $a_i, a_j \neq -1$，则 $a_i \neq a_j$

输出格式

对于每个测试用例，输出一个整数，即答案对 $998244353$ 取模的结果。

样例

输入 1

6
2
1 2
3
-1 -1 -1
4
1 -1 -1 -1
5
1 -1 -1 -1 5
6
3 -1 -1 -1 -1 4
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出 1

1
4
1
0
6
92

说明

在第一个测试用例中，车已经放置好，且满足条件：

在第二个测试用例中，有 4 种放置车的方式：

在第三个测试用例中，恰好有一种这样的方式：

在第四个测试用例中，目前已经放置了两个车：

它们之间的曼哈顿距离已经为 $8 > 5$，因此不存在满足条件的剩余车放置方案。