You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

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

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}$.

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

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$