順列 $p_1, p_2, \dots, p_n$ が与えられます。以下の操作を繰り返し行うことができます。

• 区間 $p_l, p_{l+1}, \dots, p_{l+c}$ ($l \ge 1, l+c \le n$) を選び、$p_l$ がこの区間内で最小の要素である場合、$p_{l+1}, \dots, p_{l+c}$ を任意に並び替えることができる。
• 区間 $p_l, p_{l+1}, \dots, p_{l+c}$ ($l \ge 1, l+c \le n$) を選び、$p_{l+c}$ がこの区間内で最小の要素である場合、$p_l, \dots, p_{l+c-1}$ を任意に並び替えることができる。

これらの操作を用いて得られる順列が何通りあるかを求めてください。答えは非常に大きくなる可能性があるため、998244353 で割った余りを出力してください。

入力

最初の行には、テストケースの数 $T$ ($1 \le T \le 100000$) が含まれます。 各テストケースの最初の行には、2つの整数 $n$ と $c$ ($2 \le c \le 500000, 2 \le n \le 500000$) が含まれます。すべてのテストケースにおける $n$ の合計は 500000 を超えません。 各テストケースの2行目には、順列 $p_1, \dots, p_n$ ($1 \le p_i \le n$) が含まれます。

出力

各テストケースについて、答えを 998244353 で割った余りを1行で出力してください。

入出力例

入力 1

5
5 3
3 4 2 1 5
5 4
4 2 1 3 5
5 2
4 5 3 1 2
5 3
4 3 2 1 5
5 2
2 3 1 5 4

出力 1

6
1
4
6
4