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