Dana jest permutacja $p$ o długości $n$.

Każda operacja losowo wybiera liczbę całkowitą $i$ z jednakowym prawdopodobieństwem ($1 \le i \le n$), a następnie sortuje odpowiednio przedział prefiksowy $[1, i]$ oraz przedział sufiksowy $[i + 1, n]$ permutacji $p$ w porządku rosnącym. W szczególności, gdy $i = n$, przedział sufiksowy jest pusty, co jest równoważne posortowaniu całej permutacji.

Musisz znaleźć oczekiwaną liczbę operacji potrzebnych do momentu, aż końcowa permutacja stanie się całkowicie posortowana rosnąco (to znaczy $p_j = j$).

Odpowiedź należy podać modulo $998\,244\,353$.

Wejście

To zadanie zawiera wiele przypadków testowych.

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 500$), oznaczającą długość permutacji.
• Drugi wiersz zawiera $n$ liczb całkowitych $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), reprezentujących daną permutację $p$. Gwarantuje się, że podany ciąg jest permutacją liczb $1 \sim n$.

Gwarantuje się, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $2000$.

Wyjście

Dla każdego przypadku testowego wypisz w jednym wierszu jedną liczbę całkowitą: oczekiwaną liczbę operacji modulo $998\,244\,353$.

Przykład

Wejście

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

Wyjście

748683267
2
670695427