整数配列 $a_1, \dots, a_n$ が与えられます。偶数長の連続部分列 $a_i, \dots, a_{i+2m-1}$ は、以下の条件を満たすとき good であると呼ばれます。 $$|\max(a_i, \dots, a_{i+m-1}) - \max(a_{i+m}, \dots, a_{i+2m-1})| \le k$$

整数列 $f$ を以下のように定義します。

• $f_1 = 3240$
• $f_2 = 3081$
• $f_3 = 2841$
• $f_4 = 343$
• $f_i = f_{i-1} \cdot 223 + f_{i-2} \cdot 229 + f_{i-3} \cdot f_{i-4} \cdot 239 + 17$ （$i > 4$ のとき）

すべての good な連続部分列について、$(a_{i+m-1} + 10) \cdot f_m$ の総和を計算してください。この値は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、2つの整数 $n, k$ ($1 \le n \le 5 \cdot 10^5, 0 \le k \le \min(n, 10)$) が含まれます。 次の行には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が含まれます。

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

出力

各テストケースについて、問題の答えを単一の整数として出力してください。

入出力例

入力 1

3
6 0
3 1 3 1 3 1
8 4
5 8 4 6 5 7 8 5
7 3
2 1 3 2 2 1 3

出力 1

144768
745933
448953