Gitt en permutasjon $p$ av lengde $n$.

Hver operasjon velger tilfeldig et heltall $i$ med lik sannsynlighet ($1 \le i \le n$), og sorterer deretter henholdsvis prefiksintervallet $[1, i]$ og suffiksintervallet $[i + 1, n]$ av permutasjonen $p$ i stigende rekkefølge. Spesielt, når $i = n$, er suffiksintervallet tomt, noe som tilsvarer å sortere hele permutasjonen.

Du må finne det forventede antallet operasjoner som kreves til den endelige permutasjonen blir fullstendig sortert i stigende rekkefølge (det vil si $p_j = j$).

Svaret skal oppgis modulo $998\,244\,353$.

Inndata

Dette problemet inneholder flere testtilfeller.

Den første linjen inneholder et heltall $T$ ($1 \le T \le 100$), antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder et heltall $n$ ($1 \le n \le 500$), lengden på permutasjonen.
• Den andre linjen inneholder $n$ heltall $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), som representerer den gitte permutasjonen $p$. Det er garantert at den gitte følgen er en permutasjon av $1 \sim n$.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2000$.

Utdata

For hvert testtilfelle, skriv ut én linje som inneholder ett heltall: det forventede antallet operasjoner modulo $998\,244\,353$.

Eksempel

Inndata

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

Utdata

748683267
2
670695427