C. Kevin and Puzzle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kevin enjoys logic puzzles.

He played a game with $$$n$$$ classmates who stand in a line. The $$$i$$$-th person from the left says that there are $$$a_i$$$ liars to their left (not including themselves).

Each classmate is either honest or a liar, with the restriction that no two liars can stand next to each other. Honest classmates always say the truth. Liars can say either the truth or lies, meaning their statements are considered unreliable.

Kevin wants to determine the number of distinct possible game configurations modulo $$$998\,244\,353$$$. Two configurations are considered different if at least one classmate is honest in one configuration and a liar in the other.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1\leq n \leq 2 \cdot 10^5$$$) — the number of classmates.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i \leq n$$$) — the number of liars to the left of the $$$i$$$-th person they claimed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer — the number of distinct game configurations modulo $$$998\,244\,353$$$.

Example
Input
8
3
0 1 2
5
0 0 0 0 0
5
0 0 1 1 2
5
0 1 2 3 4
5
0 0 1 1 1
5
5 1 5 2 5
1
0
4
2 3 1 1
Output
1
2
3
0
4
1
2
0
Note

We will use $$$\color{red}{\text{red}}$$$ to mark liars and $$$\color{blue}{\text{blue}}$$$ to mark honest people.

In the first test case, the only possible way is $$$(\color{red}{0},\color{blue}{1},\color{red}{2})$$$.

In the second test case, two possible ways are $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})$$$ and $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})$$$.

In the third test case, three possible ways are $$$(\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2})$$$, $$$(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2})$$$, $$$(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{blue}{1},\color{red}{2})$$$.