L. MEX问题
time limit per test
10 s
memory limit per test
512 megabytes
input
standard input
output
standard output

我们称一个整数序列 $$$x_1,x_2,\dots,x_k$$$ 为美丽的，当且仅当对于所有 $$$i(1 \leq i \leq k)$$$，都有 $$$x_i-\mathrm{MEX} (x_1,x_2,\dots,x_i)\leq 1$$$ 成立，其中 $$$\mathrm{MEX} (x_1,\dots,x_k)$$$ 表示最小的不在集合 $$$x_1,\dots,x_k$$$ 中出现的非负整数。例如，$$$\mathrm{MEX} (1,0,1,3)=2$$$，$$$\mathrm{MEX}(2,1,5)=0$$$。

给定一个长度为 $$$n$$$ 的非负整数序列 $$$a$$$，计算它有多少个非空子序列是美丽的，答案对 $$$998244353$$$ 取模。其中序列 $$$x$$$ 是序列 $$$y$$$ 的子序列，当且仅当从 $$$y$$$ 中删除若干（可以为 $$$0$$$）个元素后能得到 $$$x$$$。

Input

多组数据输入。

第一行有一个整数 $$$t(1 \leq t \leq 10^5)$$$ 表示数据组数。

每组数据的第一行有一个整数 $$$n(1 \leq n \leq 5\cdot 10^5)$$$，第二行有 $$$n$$$ 个整数 $$$a_1,a_2,\dots,a_n(0 \leq a_i \leq n)$$$。

所有数据的 $$$n$$$ 的总和不超过 $$$5\cdot 10^5$$$。

Output

对于每组数据，输出一个整数表示答案。

Example
Input
4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3
Output
5
3
31
7