給定一個整數陣列 $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$

請計算所有好的子區段中 $(a_{i+m-1} + 10) \cdot f_m$ 的總和。由於此數值可能很大，請將結果對 $998\,244\,353$ 取模。

輸入格式

第一行包含一個整數 $t$ ($1 \le t \le 10^4$)，代表測試資料的組數。接著為各組測試資料的描述。

每組測試資料的第一行包含兩個整數 $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