Gefin er umröðun $p$ af lengd $n$.

Í hverri aðgerð er heiltala $i$ valin af handahófi með jöfnum líkum ($1 \le i \le n$), og síðan er forskeytisbilinu $[1, i]$ og viðskeytisbilinu $[i + 1, n]$ í umröðuninni $p$ raðað í hækkandi röð hvoru fyrir sig. Sérstaklega, þegar $i = n$, er viðskeytisbilið tómt, sem jafngildir því að raða allri umröðuninni.

Þú þarft að finna væntigildi fjölda aðgerða sem þarf þar til lokaumröðunin er orðin fullkomlega röðuð í hækkandi röð (það er, $p_j = j$).

Svarið skal gefa upp mát $998\,244\,353$.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik.

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 100$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 500$), lengd umröðunarinnar.
• Önnur línan inniheldur $n$ heiltölur $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), sem tákna gefnu umröðunina $p$. Tryggt er að gefna runan sé umröðun á $1 \sim n$.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2000$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu: væntigildi fjölda aðgerða mát $998\,244\,353$.

Dæmi

Inntak

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

Úttak

748683267
2
670695427