给定一个整数数组 $a_1, \dots, a_n$。如果一个偶数长度的子段 $a_i, \dots, a_{i+2m-1}$ 满足 $|\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