Se da una permutación $p$ de longitud $n$.

Cada operación elige aleatoriamente un entero $i$ con igual probabilidad ($1 \le i \le n$), y luego ordena el intervalo prefijo $[1, i]$ y el intervalo sufijo $[i + 1, n]$ de la permutación $p$ en orden ascendente, respectivamente. En particular, cuando $i = n$, el intervalo sufijo está vacío, lo cual equivale a ordenar toda la permutación.

Debes encontrar el número esperado de operaciones necesarias hasta que la permutación final quede completamente ordenada en orden ascendente (es decir, $p_j = j$).

La respuesta debe tomarse módulo $998\,244\,353$.

Entrada

Este problema contiene múltiples casos de prueba.

La primera línea contiene un entero $T$ ($1 \le T \le 100$), el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene un entero $n$ ($1 \le n \le 500$), la longitud de la permutación.
• La segunda línea contiene $n$ enteros $p_1, p_2, \cdots, p_n$ ($1 \le p_j \le n$), que representan la permutación dada $p$. Se garantiza que la secuencia dada es una permutación de $1 \sim n$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2000$.

Salida

Para cada caso de prueba, imprime una línea con un entero: el número esperado de operaciones módulo $998\,244\,353$.

Ejemplo

Entrada

3
3
3 1 2
2
2 1
5
3 2 5 1 4

Salida

748683267
2
670695427