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.