F. F(x,l,r)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$[a_1,a_2,\dots,a_n]$$$ of length $$$n$$$ and an integer $$$k$$$.

In one operation, you can choose any integer $$$y$$$ and a range $$$[l,r]$$$, such that $$$1 \leq l \leq r \leq n$$$ and $$$r-l+1 \leq k$$$, and assign $$$a_i:=y$$$ for all $$$i \in [l,r]$$$.

Let's define $$$F(x,l,r)$$$ as the minimum number of operations to make $$$a_i\leq x$$$ for all $$$i \in [l,r]$$$. Find the following sum:

$$$$$$ \sum_{x=1}^n \sum_{l=1}^n \sum_{r=l}^n F(x,l,r) $$$$$$

As the answer can be very large, print it modulo $$$998244353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^4$$$). The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq n$$$).

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

Output

Print a single integer  — the answer modulo $$$998244353$$$.

Example
Input
4
3 2
1 1 1
3 1
1 2 3
3 3
3 3 3
12 4
3 1 4 1 5 9 2 6 5 3 5 9
Output
0
10
12
648