You are given a multiset $$$a$$$, which consists of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. You would like to generate a new multiset $$$s$$$ through the following procedure:

Partition $$$a$$$ into any number of non-empty multisets $$$x_1,x_2,\ldots,x_k$$$, such that each element of $$$a$$$ belongs to exactly one of these multisets.
Initially, $$$s$$$ is empty. From each $$$x_i$$$, choose one of its modes$$$^{\text{∗}}$$$ and insert it into $$$s$$$.

Please count the number of different multisets $$$s$$$ that can be generated through the procedure, modulo $$$998\,244\,353$$$.

Please note that the number of different multisets is counted, which means that the order of elements does not matter. However, the count of each element does matter, i.e. $$$\{1,1,2\},\{1,2\},\{1,1,2,2\}$$$ are all considered different.

$$$^{\text{∗}}$$$The mode of a multiset is defined as the element which appears the most; if several elements are tied as the maximum, then all of them are considered modes.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le5000$$$) — the size of multiset $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, print one line containing a single integer — the number of different multisets you can obtain, modulo $$$998\,244\,353$$$.

Note

In the first test case, any non-empty subset of $$$\{1,2,3\}$$$ can be achieved, for a total of $$$7$$$ multisets.

In the third test case, we can generate $$$4$$$ different multisets:

Partition the elements into set $$$\{1,2,2\}$$$, resulting in multiset $$$\{2\}$$$.
Partition the elements into sets $$$\{1,2\},\{2\}$$$, resulting in multiset $$$\{2,2\}$$$.
Partition the elements into sets $$$\{1\},\{2,2\}$$$, resulting in multiset $$$\{1,2\}$$$.
Partition the elements into sets $$$\{1\},\{2\},\{2\}$$$, resulting in multiset $$$\{1,2,2\}$$$.

It can be proven that no other multisets are possible.

Idx	Name	Rating
A	Cyclic Merging	1300
B	Marble Council	1900
C	Binary Wine	2000
D	Path Split	2500
E	Rainbow Branch	3200
F	Arctic Acquisition	3500

Codeforces Round 1064 (Div. 1)