You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Given a cyclic array $$$a$$$ of size $$$n$$$, where $$$a_i$$$ is the value of $$$a$$$ in the $$$i$$$-th position, there may be repeated values. Let us define that a permutation of $$$a$$$ is equal to another permutation of $$$a$$$ if and only if their values are the same for each position $$$i$$$ or we can transform them to each other by performing some cyclic rotation. Let us define for a cyclic array $$$b$$$ its number of components as the number of connected components in a graph, where the vertices are the positions of $$$b$$$ and we add an edge between each pair of adjacent positions of $$$b$$$ with equal values (note that in a cyclic array the first and last position are also adjacents).

Find the expected value of components of a permutation of $$$a$$$ if we select it equiprobably over the set of all the different permutations of $$$a$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of the cyclic array $$$a$$$.

The second line of each test case contains $$$n$$$ integers, the $$$i$$$-th of them is the value $$$a_i$$$ ($$$1 \le a_i \le n$$$).

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

It is guaranteed that the total number of different permutations of $$$a$$$ is not divisible by $$$M$$$

## Output Format
For each test case print a single integer — the expected value of components of a permutation of $$$a$$$ if we select it equiprobably over the set of all the different permutations of $$$a$$$ modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Examples
```input
5
4
1 1 1 1
4
1 1 2 1
4
1 2 1 2
5
4 3 2 5 1
12
1 3 2 3 2 1 3 3 1 3 3 2
```
```output
1
2
3
5
358642921
```

## Note
In the first test case there is only $$$1$$$ different permutation of $$$a$$$:

- $$$[1, 1, 1, 1]$$$ has $$$1$$$ component.
- Therefore the expected value of components is $$$\frac{1}{1} = 1$$$

In the second test case there are $$$4$$$ ways to permute the cyclic array $$$a$$$, but there is only $$$1$$$ different permutation of $$$a$$$:

- $$$[1, 1, 1, 2]$$$, $$$[1, 1, 2, 1]$$$, $$$[1, 2, 1, 1]$$$ and $$$[2, 1, 1, 1]$$$ are the same permutation and have $$$2$$$ components.
- Therefore the expected value of components is $$$\frac{2}{1} = 2$$$

In the third test case there are $$$6$$$ ways to permute the cyclic array $$$a$$$, but there are only $$$2$$$ different permutations of $$$a$$$:

- $$$[1, 1, 2, 2]$$$, $$$[2, 1, 1, 2]$$$, $$$[2, 2, 1, 1]$$$ and $$$[1, 2, 2, 1]$$$ are the same permutation and have $$$2$$$ components.
- $$$[1, 2, 1, 2]$$$ and $$$[2, 1, 2, 1]$$$ are the same permutation and have $$$4$$$ components.
- Therefore the expected value of components is $$$\frac{2+4}{2} = \frac{6}{2} = 3$$$

In the fourth test case there are $$$120$$$ ways to permute the cyclic array $$$a$$$, but there are only $$$24$$$ different permutations of $$$a$$$:

- Any permutation of $$$a$$$ has $$$5$$$ components.
- Therefore the expected value of components is $$$\frac{24\cdot 5}{24} = \frac{120}{24} = 5$$$

Now solve the problem and return the code.