Ұзындығы $n$ болатын $p$ алмастыруы берілген.

Әрбір операцияда бірдей ықтималдықпен кездейсоқ $i$ ($1 \le i \le n$) бүтін саны таңдалады, содан кейін $p$ алмастыруының $[1, i]$ префикстік аралығы мен $[i + 1, n]$ суффикстік аралығы сәйкесінше өсу ретімен сұрыпталады. Дербес жағдайда, $i = n$ болғанда суффикстік аралық бос болады, бұл бүкіл алмастыруды сұрыптаумен пара-пар.

Соңғы алмастыру толығымен өсу ретімен сұрыпталғанға дейін (яғни $p_j = j$ болғанша) қажет болатын операциялар санының математикалық күтімін табу керек.

Жауапты $998\,244\,353$ модулі бойынша шығарыңыз.

Кіріс деректері

Бұл есеп бірнеше тест жағдайларынан тұрады.

Бірінші жолда тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 100$) берілген.

Әрбір тест жағдайы үшін:

• Бірінші жолда алмастырудың ұзындығын білдіретін бір бүтін сан $n$ ($1 \le n \le 500$) берілген.
• Екінші жолда берілген $p$ алмастыруын сипаттайтын $n$ бүтін сан $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$) берілген. Берілген тізбек $1 \sim n$ сандарының алмастыруы екеніне кепілдік беріледі.

Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $2000$-нан аспайтынына кепілдік беріледі.

Шығыс деректері

Әрбір тест жағдайы үшін бір жолға бір бүтін санды — операциялар санының математикалық күтімін $998\,244\,353$ модулі бойынша шығарыңыз.

Мысал

Кіріс деректері

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

Шығыс деректері

748683267
2
670695427