Задано перестановку $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