Kevin 喜欢逻辑谜题。

他和排成一排的 $n$ 个同学玩了一个游戏。从左往右数第 $i$ 个人说，在他们的左边（不包括他们自己）有 $a_i$ 个说谎者。

每个同学要么是诚实的，要么是说谎者，且满足任意两个说谎者不能相邻。诚实的同学总是说真话。说谎者既可以说真话也可以说假话，这意味着他们的言论被认为是不可靠的。

Kevin 想要确定所有可能的游戏配置数量，结果对 $998\,244\,353$ 取模。如果在一种配置中至少有一个同学是诚实的，而在另一种配置中是说谎者，则认为这两种配置是不同的。

输入格式

每个测试点包含多个测试样例。第一行包含测试样例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试样例的描述。

每个测试样例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) — 同学的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) — 第 $i$ 个人声称的其左侧说谎者的数量。

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

输出格式

对于每个测试样例，输出一个整数 — 可能的游戏配置数量对 $998\,244\,353$ 取模后的结果。

样例

输入样例 1

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

输出样例 1

1
2
3
0
4
1
2
0

说明

我们将用红色标记说谎者，用蓝色标记诚实的人。

在第一个测试样例中，唯一可能的情况是 $(\color{red}{0}, \color{blue}{1}, \color{red}{2})$。

在第二个测试样例中，两种可能的情况是 $(\color{blue}{0}, \color{blue}{0}, \color{blue}{0}, \color{blue}{0}, \color{blue}{0})$ 和 $(\color{blue}{0}, \color{blue}{0}, \color{blue}{0}, \color{blue}{0}, \color{red}{0})$。

在第三个测试样例中，三种可能的情况是 $(\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{blue}{1}, \color{red}{2})$ 和 $(\color{blue}{0}, \color{red}{0}, \color{blue}{1}, \color{red}{1}, \color{blue}{2})$。