D. Tripartite Graph
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little M has obtained a tripartite graph.

An undirected graph is a tripartite graph if and only if there exists a way to color each vertex of the graph with one of three colors: $$$1, 2, 3$$$, such that the colors of the two vertices connected by each edge are different.

For a permutation $$$p$$$ of length $$$n$$$, Little A generates a graph with $$$n$$$ vertices as follows:

For $$$1 \leq i \lt j \leq n$$$, if $$$p_i \gt p_j$$$, then an undirected edge $$$(i,j)$$$ is added to the graph; otherwise, there is no undirected edge $$$(i,j)$$$ in the graph.

Now, given a permutation $$$q$$$ of length $$$n$$$, how many permutations $$$p$$$ of length $$$n$$$ exist such that the lexicographical order of $$$p$$$ is greater than that of $$$q$$$, and the graph generated by $$$p$$$ is a tripartite graph? The answer should be given modulo $$$998244353$$$.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 300)$$$, indicating the number of test cases.

For each test case, the first line contains a positive integer $$$n$$$ $$$(1 \leq n \leq 300)$$$, representing the length of the permutation.

The second line contains $$$n$$$ integers $$$q_1, q_2, \cdots, q_n$$$ $$$(1 \leq q_i \leq n)$$$, with the same meaning as described in the problem. It is guaranteed that $$$q_i \neq q_j$$$ for $$$i \neq j$$$, meaning that $$$q$$$ is a permutation.

Output

For each test case, output a single line containing an integer representing the answer, modulo $$$998244353$$$.

Example
Input
2
5
1 2 3 4 5
5
1 3 2 4 5
Output
102
96