Bạn được cho một mảng số nguyên $a_1, \dots, a_n$. Một đoạn con có độ dài chẵn $a_i, \dots, a_{i+2m-1}$ được gọi là tốt nếu $|\max(a_i, \dots, a_{i+m-1}) - \max(a_{i+m}, \dots, a_{i+2m-1})| \le k$.

Định nghĩa dãy số nguyên $f$ như sau:

• $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$ với $i > 4$

Hãy tính tổng $(a_{i+m-1} + 10) \cdot f_m$ trên tất cả các đoạn con tốt. Vì số này có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu. Tiếp theo là mô tả các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n, k$ ($1 \le n \le 5 \cdot 10^5, 0 \le k \le \min(n, 10)$).

Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — đáp án của bài toán.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

144768
745933
448953