题目描述

研究员 Mira 正在校准一台双段观测仪。它会从一个整数数组中取出偶数长度的连续片段，把片段分成左右两半，并比较两半的最大值。

给定整数数组 $a_1,a_2,\ldots,a_n$。对于一个长度为 $2m$ 的连续子段

$$a_i,a_{i+1},\ldots,a_{i+2m-1},$$

若满足

$$\left|\max(a_i,\ldots,a_{i+m-1})-\max(a_{i+m},\ldots,a_{i+2m-1})\right|\le k,$$

则称这个子段是好的。

定义整数序列 $f$ 如下：

• $f_1=3240$；
• $f_2=3081$；
• $f_3=2841$；
• $f_4=343$；
• 当 $i>4$ 时，

$$f_i=f_{i-1}\cdot 223+f_{i-2}\cdot 229+f_{i-3}\cdot f_{i-4}\cdot 239+17.$$

请在所有好的子段中，计算

$$(a_{i+m-1}+10)\cdot f_m$$

的总和。由于结果可能很大，请输出它对 $998244353$ 取模后的值。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

接下来依次给出每组测试数据。

每组测试数据第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

保证所有测试数据中 $n$ 的总和不超过 $5\cdot 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示答案。

数据范围

• $1\le t\le 10^4$；
• $1\le n\le 5\cdot 10^5$；
• $0\le k\le \min(n,10)$；
• $1\le a_i\le n$；
• 所有测试数据中 $\sum n\le 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

输出

144768
745933
448953