Dana jest permutacja $p_1, p_2, \dots, p_n$. Możesz wielokrotnie wykonywać następujące operacje:

• Wybierz przedział $p_l, p_{l+1}, \dots, p_{l+c}$ ($l \ge 1, l+c \le n$), w którym $p_l$ jest najmniejszym elementem; możesz dowolnie permutować elementy $p_{l+1}, \dots, p_{l+c}$.
• Wybierz przedział $p_l, p_{l+1}, \dots, p_{l+c}$ ($l \ge 1, l+c \le n$), w którym $p_{l+c}$ jest najmniejszym elementem; możesz dowolnie permutować elementy $p_l, \dots, p_{l+c-1}$.

Chcesz wiedzieć, ile różnych permutacji możesz uzyskać, stosując te operacje. Wynik może być duży, więc wyprowadź go modulo 998244353.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$ oznaczającą liczbę zestawów danych ($1 \le T \le 100000$).

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $n$ oraz $c$ ($2 \le c \le 500000, 2 \le n \le 500000$). Suma $n$ dla wszystkich zestawów danych nie przekracza 500000.

Druga linia każdego zestawu danych zawiera permutację $p_1, \dots, p_n$ ($1 \le p_i \le n$).

Wyjście

Dla każdego zestawu danych wyprowadź w jednej linii wynik modulo 998244353.

Przykład

Wejście 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

Wyjście 1

6
1
4
6
4