P17493 [ICPC 2026 Wuhan I] Sort

Given a permutation $p$ of length $n$. Each operation randomly chooses an integer $i$ with equal probability ($1 \le i \le n$), and then sorts the prefix interval $[1,i]$ and the suffix interval $[i+1,n]$ of the permutation $p$ in ascending order, respectively. In particular, when $i=n$, the suffix interval is empty, which is equivalent to sorting the entire permutation. You need to find the expected number of operations required until the final permutation becomes completely sorted in ascending order (that is, $p_j=j$). The answer should be taken modulo $998244353$.

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 100$), the number of test cases. For each test case: - The first line contains an integer $n$ ($1 \le n \le 500$), the length of the permutation. - The second line contains $n$ integers $p_1,p_2,\cdots,p_n$ ($1 \le p_j \le n$), representing the given permutation $p$. It is guaranteed that the given sequence is a permutation of $1\sim n$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

For each test case, output one line containing an integer, the expected number of operations modulo $998244353$.