G. Generalized star graphs
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Z-tube Cat said: "No more counting dollars, we'll be counting stars……"

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

A generalized star graph is defined as a labeled unrooted tree satisfying: the number of nodes with degree $$$1$$$ is greater than or equal to the weight of the node with the maximum degree. If there are multiple nodes with the maximum degree, take the largest weight among them.

Please count the number of generalized star graphs $$$^{\text{*}}$$$ that can be formed by these $$$n$$$ nodes, modulo $$$998244353$$$.

Excessive modulo operations may cause severe performance overhead. Please reduce unnecessary modulo operations!

$$$^{\text{*}}$$$ Two labeled unrooted trees are considered different if and only if there exists at least one pair of labels $$$(u, v)$$$ such that they are connected by an edge in one tree but not in the other.

Input

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

For each test case:

The first line contains an integer $$$n$$$ ($$$3 \le n \le 250$$$), 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 $$$a_i$$$ denotes the weight of node $$$i$$$.

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

Output

For each test case, output a single integer on a line — the number of generalized star graphs that can be formed by these $$$n$$$ nodes, modulo $$$998244353$$$.

Example
Input
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
6
5
31108248
Note

For the first test case in the sample, all generalized star graphs formed by these $$$6$$$ nodes are shown below:

For the second test case in the sample, all generalized star graphs formed by these $$$4$$$ nodes are shown below: