أُعطيت تبديلة $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