让我们调用整数序列 $$$x_1, x_2, \dots, x_k$$$ MEX 正确,如果对于所有 $$$i$$$ ($$$1 \le i \le k$$$) $$$|x_i - \operatorname{MEX}(x_1, x_2, \dots, x_i)| \le 1$$$ 成立。其中 $$$\operatorname{MEX}(x_1, \dots, x_k)$$$ 是不属于集合 $$$x_1, \dots, x_k$$$ 的最小非负整数。例如,$$$\operatorname{MEX}(1, 0, 1, 3) = 2$$$ 和 $$$\operatorname{MEX}(2, 1, 5) = 0$$$。
给定一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$。计算给定数组的非空 MEX 正确子序列的数量。子序列的数量可能非常大,因此将其打印为 $$$998244353$$$ 模。
注意:数组 $$$a$$$ 的子序列是满足约束 $$$1 \le i_1 < i_2 < \dots < i_m \le n$$$ 的序列 $$$[a_{i_1}, a_{i_2}, \dots, a_{i_m}]$$$。如果选择索引序列 $$$[i_1, i_2, \dots, i_m]$$$ 的两种不同方式产生相同的子序列,则应对所得子序列进行两次计数(即,如果索引序列 $$$[i_1, i_2, \dots, i_m]$$$ 不相同,则两个子序列不同)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 给定数组的非空 MEX 正确子序列的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
4 3 0 2 1 2 1 0 5 0 0 0 0 0 4 0 1 2 3
输出 #1
4 2 31 7
注意
在第一个示例中,有效子序列是 $$$[0]$$$、$$$[1]$$$、$$$[0,1]$$$ 和 $$$[0,2]$$$。
在第二个示例中,有效子序列是 $$$[0]$$$ 和 $$$[1]$$$。
在第三个示例中,任何非空子序列都是有效的。