Givet en permutation $p$ av längd $n$.

Varje operation väljer slumpmässigt ett heltal $i$ med lika sannolikhet ($1 \le i \le n$), och sorterar därefter prefixintervallet $[1, i]$ respektive suffixintervallet $[i + 1, n]$ av permutationen $p$ i stigande ordning. Speciellt, när $i = n$ är suffixintervallet tomt, vilket är ekvivalent med att sortera hela permutationen.

Du ska beräkna det förväntade antalet operationer som krävs tills den slutliga permutationen blir helt sorterad i stigande ordning (det vill säga $p_j = j$).

Svaret ska anges modulo $998\,244\,353$.

Indata

Detta problem innehåller flera testfall.

Den första raden innehåller ett heltal $T$ ($1 \le T \le 100$), antalet testfall.

För varje testfall:

• Den första raden innehåller ett heltal $n$ ($1 \le n \le 500$), längden på permutationen.
• Den andra raden innehåller $n$ heltal $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), som representerar den givna permutationen $p$. Det garanteras att den givna talföljden är en permutation av $1 \sim n$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2000$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett heltal: det förväntade antalet operationer modulo $998\,244\,353$.

Exempel

Indata

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

Utdata

748683267
2
670695427