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$) が含まれる。

2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$) が含まれる。これは、$i$ 番目の人が主張した、自分より左側にいる嘘つきの人数である。

すべてのテストケースにおける $n$ の総和は $2 \cdot 10^5$ を超えないことが保証される。

出力

各テストケースについて、考えられるゲームの構成の総数を $998\,244\,353$ で割った余りを1行で出力せよ。

入出力例

入力 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

注記

嘘つきを赤色、正直者を青色で表すことにする。

最初のテストケースでは、唯一の可能な方法は $(0, 1, 2)$ である。

2番目のテストケースでは、2つの可能な方法は $(0, 0, 0, 0, 0)$ と $(0, 0, 0, 0, 0)$ である。

3番目のテストケースでは、3つの可能な方法は $(0, 0, 1, 1, 2)$、$(0, 0, 1, 1, 2)$、$(0, 0, 1, 1, 2)$ である。