E. Fun is Counting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$.

An array $$$b$$$ of size $$$n$$$ is considered valid if and only if:

  • $$$1 \le b_i \le n$$$ for all $$$1 \le i \le n$$$;
  • If $$$b_i$$$ is removed from the array $$$b$$$, there are exactly $$$a_i$$$ different numbers in the array $$$b$$$.

Count the number of different multisets $$$\{b_1,b_2,\ldots,b_n\}$$$ composed of each valid array $$$b$$$ modulo $$$998244353$$$.

Note that the order of numbers is not important in a multiset. For example, $$$\{1,1,2\}$$$ and $$$\{2,1,1\}$$$ are considered the same, but $$$\{1,1,2\}$$$ and $$$\{2,1,2\}$$$ are not.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$1 \le a_{i} \le n-1$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output in a new line  — the number of different multisets $$$\{b_1,b_2,\ldots,b_n\}$$$ composed of each valid array $$$b$$$ modulo $$$998244353$$$.

Example
Input
6
2
1 1
3
2 2 2
3
2 1 2
4
1 2 3 2
4
3 3 2 2
6
3 3 2 2 3 3
Output
3
1
6
0
12
60
Note

In the first test case, there are four valid arrays  — $$$[1,1]$$$,$$$[2,2]$$$,$$$[1,2]$$$ and $$$[2,1]$$$. Thus, there are three different multisets $$$\{1,1\}$$$,$$$\{2,2\}$$$ and $$$\{1,2\}$$$.

In the second test case, there is only one multiset $$$\{1,2,3\}$$$.