On vous donne une permutation $p$ de longueur $n$.

Chaque opération choisit aléatoirement un entier $i$ de manière équiprobable ($1 \le i \le n$), puis trie respectivement l'intervalle préfixe $[1, i]$ et l'intervalle suffixe $[i + 1, n]$ de la permutation $p$ par ordre croissant. En particulier, lorsque $i = n$, l'intervalle suffixe est vide, ce qui équivaut à trier toute la permutation.

Vous devez trouver le nombre espéré d'opérations nécessaires jusqu'à ce que la permutation finale soit complètement triée par ordre croissant (c'est-à-dire $p_j = j$).

La réponse doit être donnée modulo $998\,244\,353$.

Entrée

Ce problème contient plusieurs cas de test.

La première ligne contient un entier $T$ ($1 \le T \le 100$), le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient un entier $n$ ($1 \le n \le 500$), la longueur de la permutation.
• La deuxième ligne contient $n$ entiers $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), représentant la permutation donnée $p$. Il est garanti que la séquence donnée est une permutation de $1 \sim n$.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2000$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un entier : le nombre espéré d'opérations modulo $998\,244\,353$.

Exemple

Entrée

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

Sortie

748683267
2
670695427