נתונה תמורה $p$ באורך $n$.

כל פעולה בוחרת באקראי ובהסתברות שווה מספר שלם $i$ ($1 \le i \le n$), ולאחר מכן ממיינת את קטע הרישא $[1, i]$ ואת קטע הסיפא $[i + 1, n]$ של התמורה $p$ בסדר עולה, בהתאמה. בפרט, כאשר $i = n$, קטע הסיפא ריק, דבר השקול למיון התמורה כולה.

עליכם למצוא את תוחלת מספר הפעולות הנדרשות עד שהתמורה הסופית תהיה ממוינת לחלוטין בסדר עולה (כלומר, $p_j = j$).

יש להחזיר את התשובה מודולו $998\,244\,353$.

קלט

בעיה זו מכילה מספר מקרי בדיקה.

השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 100$), מספר מקרי הבדיקה.

עבור כל מקרה בדיקה:

• השורה הראשונה מכילה מספר שלם $n$ ($1 \le n \le 500$), אורך התמורה.
• השורה השנייה מכילה $n$ מספרים שלמים $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), המייצגים את התמורה הנתונה $p$. מובטח כי הסדרה הנתונה היא תמורה של $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