Given $n$ nodes, where node $i$ has a weight $a_i$.

A "generalized chrysanthemum graph" is defined as a labeled unrooted tree that satisfies the condition: "the number of nodes with degree 1 is greater than or equal to the weight of the node with the maximum degree." Specifically, if there are multiple nodes with the maximum degree, we take the maximum weight among them.

Please calculate the number of ways to form a generalized chrysanthemum graph with these $n$ nodes, modulo 998244353.

Note that excessive modulo operations can cause significant performance overhead; please reduce unnecessary modulo operations!

Two generalized chrysanthemum graphs are considered different (i.e., two labeled unrooted trees are different) if and only if there exist two labels $u, v$ such that the node labeled $u$ and the node labeled $v$ are connected by an edge in one generalized chrysanthemum graph, but are not connected by an edge in the other.

Input

Each test case contains multiple test data. The first line contains an integer $T$ ($1 \le T \le 50$), representing the number of test cases.

For each test case: The first line contains an integer $n$ ($3 \le n \le 250$), representing the total number of nodes. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where the $i$-th integer $a_i$ represents the weight of the node labeled $i$.

It is guaranteed that the sum of $n$ over all test cases in each test file does not exceed 250.

Output

For each test case, output a single integer on a new line, representing the number of ways to form a generalized chrysanthemum graph with these $n$ nodes, modulo 998244353.

Examples

Input 1

3
6
5 5 5 5 5 5
4
2 3 2 4
10
5 4 10 3 10 1 5 8 8 1

Output 1

6
5
31108248

Note

For the first test case in the example, all ways to form a generalized chrysanthemum graph with these 6 nodes are as follows:

For the second test case in the example, all ways to form a generalized chrysanthemum graph with these 4 nodes are as follows: