D. Hard Problem
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given an integer array $$$a_1, \ldots, a_n$$$. A subsegment of even length $$$a_i,\ldots, a_{i + 2m - 1}$$$ is called good if $$$\left|\max(a_i,\dots, a_{i + m - 1}) - \max(a_{i + m}, \ldots, a_{i + 2m - 1})\right| \leq k$$$.

Let us define an integer sequence $$$f$$$ as follows:

  • $$$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$$$ for $$$i \gt 4$$$

Calculate the sum $$$(a_{i+m-1} + 10) \cdot f_{m}$$$ among all good subsegments. Since this number can be large, print it modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$0 \leq k \leq \min (n, 10)$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print a single integer — the answer to the problem.

Example
Input
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
Output
144768
745933
448953