给定一个数组 $a_1, a_2, \dots, a_n$。

你需要求出将该数组划分为若干个非空子段的方法数，使得这些子段的 MEX 值全部相等。子段 $[l \dots r]$ 的 MEX 定义为不在该子段中出现的最小非负整数 $x$。

由于这个数字可能非常大，你只需要输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 300\,000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示给定数组中整数的个数。

每个测试用例的下一行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$)，表示给定的数组。

保证所有测试用例的 $n$ 之和不超过 $300\,000$。

输出格式

对于每个测试用例，输出一个整数：将给定数组划分为 MEX 值相等的非空子段的方法数，对 $998\,244\,353$ 取模。

样例

样例输入 1

4
6
0 0 0 1 1 1
5
0 1 0 1 0
4
0 0 0 0
3
3 3 3

样例输出 1

1
3
8
4