F1. 小排列问题（简单版本）

时间限制：2 秒
内存限制：256 兆字节

在简单版本中，$a_i$ 的取值范围是 $[0, n]$；在困难版本中，$a_i$ 的取值范围是 $[-1, n]$，并且好排列的定义略有不同。只有解决了所有版本的题目，你才能进行 Hack。

你有一个整数 $n$ 和一个数组 $a_1, a_2, \dots, a_n$，其中每个 $a_i$ 都在 $[0, n]$ 范围内。

一个 $[1, 2, \dots, n]$ 的排列 $p_1, p_2, \dots, p_n$ 被称为好的，如果对于每个 $i$，以下条件成立：

在 $[p_1, p_2, \dots, p_i]$ 中，数值 $\le i$ 的个数恰好为 $a_i$。

请计算好排列的数量，结果对 $998244353$ 取模。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述：

• 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$），描述好排列的条件。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一行，包含好排列的数量（对 $998244353$ 取模）。

示例

输入

5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15

输出

1
4
0
0
532305727

示例说明

在第一个测试用例中，唯一的好排列是 $[1,2,3,4,5]$。

在第二个测试用例中，有 $4$ 个好排列：

• $[2,1,5,6,3,4]$
• $[2,1,5,6,4,3]$
• $[2,1,6,5,3,4]$
• $[2,1,6,5,4,3]$

例如，$[2,1,5,6,3,4]$ 是好的，因为：

• $a_1 = 0$，在 $[p_1] = [2]$ 中 $\le 1$ 的个数为 $0$；
• $a_2 = 2$，在 $[p_1,p_2] = [2,1]$ 中 $\le 2$ 的个数为 $2$；
• $a_3 = 2$，在 $[p_1,p_2,p_3] = [2,1,5]$ 中 $\le 3$ 的个数为 $2$；
• $a_4 = 2$，在 $[p_1,p_2,p_3,p_4] = [2,1,5,6]$ 中 $\le 4$ 的个数为 $2$；
• $a_5 = 4$，在 $[p_1,p_2,p_3,p_4,p_5] = [2,1,5,6,3]$ 中 $\le 5$ 的个数为 $4$；
• $a_6 = 6$，在 $[p_1,p_2,p_3,p_4,p_5,p_6] = [2,1,5,6,3,4]$ 中 $\le 6$ 的个数为 $6$。

在第三个测试用例中，不存在好排列，因为没有任何排列能使 $a_6 = 5$（在 $[p_1, \dots, p_6]$ 中 $\le 6$ 的个数只能为 $6$）。