Kevinは論理パズルを楽しんでいる。 彼は一列に並んだ $n$ 人のクラスメートとゲームをした。左から $i$ 番目の人は、自分より左側に（自分自身を含まない）$a_i$ 人の嘘つきがいると主張している。

各クラスメートは正直者か嘘つきのいずれかであり、「嘘つき同士が隣り合うことはない」という制約がある。正直者は常に真実を語る。嘘つきは真実を語ることも嘘をつくこともあり、彼らの発言は信頼できないものとして扱われる。

Kevinは、考えられるゲームの構成が何通りあるかを $998244353$ で割った余りを求めたい。2つの構成は、少なくとも1人のクラスメートが一方では正直者、もう一方では嘘つきである場合に異なるとみなされる。

入力

各テストケースには複数のテストケースが含まれる。最初の行にはテストケースの数 $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$ を超えないことが保証される。

出力

各テストケースについて、考えられるゲームの構成の数を $998244353$ で割った余りを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

注記

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

最初のテストケースでは、唯一の可能な構成は以下の通りである。 - 正直者, 正直者, 正直者

2番目のテストケースでは、2つの可能な構成は以下の通りである。 - 正直者, 正直者, 正直者, 正直者, 正直者 - 嘘つき, 正直者, 正直者, 正直者, 正直者

3番目のテストケースでは、3つの可能な構成は以下の通りである。 - 正直者, 正直者, 嘘つき, 正直者, 嘘つき - 正直者, 正直者, 嘘つき, 嘘つき, 正直者 - 嘘つき, 正直者, 正直者, 嘘つき, 正直者