정수 배열 $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$를 만족할 때 좋은(good) 구간이라고 합니다.

정수 수열 $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