Annettuna on pituutta $n$ oleva permutaatio $p$.

Jokaisella operaatiolla valitaan satunnaisesti ja yhtä suurella todennäköisyydellä kokonaisluku $i$ ($1 \le i \le n$), ja sen jälkeen permutaation $p$ alkuväli $[1, i]$ ja loppuväli $[i + 1, n]$ järjestetään kumpikin erikseen nousevaan järjestykseen. Erityisesti kun $i = n$, loppuväli on tyhjä, mikä vastaa koko permutaation järjestämistä.

Sinun tulee määrittää odotusarvo sille, kuinka monta operaatiota tarvitaan, kunnes permutaatio on kokonaan nousevassa järjestyksessä (eli $p_j = j$).

Vastaus tulee ilmoittaa modulo $998\,244\,353$.

Syöte

Tässä tehtävässä on useita testitapauksia.

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), testitapausten lukumäärän.

Jokaisessa testitapauksessa:

• Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 500$), permutaation pituuden.
• Toinen rivi sisältää $n$ kokonaislukua $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), jotka kuvaavat annetun permutaation $p$. On taattu, että annettu lukujono on lukujen $1 \sim n$ permutaatio.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2000$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: operaatioiden lukumäärän odotusarvon modulo $998\,244\,353$.

Esimerkki

Syöte

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

Tuloste

748683267
2
670695427