F. Survival of the Fated
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are organizing a tournament for $$$n$$$ gladiators. The $$$i$$$-th gladiator has a strength level $$$a_i$$$.

The tournament consists of exactly $$$n - 1$$$ duels. In each duel:

  • Two distinct gladiators are chosen uniformly at random from those remaining in the tournament. Let their strengths be $$$x$$$ and $$$y$$$. Note that two distinct gladiators may have equal strengths.
  • The duel generates a brutality of $$$|x - y|$$$.
  • One of the two gladiators is chosen uniformly at random to be eliminated, while the other remains in the tournament.

The process continues until only one gladiator remains. Compute the expected total brutality of the tournament modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of gladiators.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the strength levels of the gladiators.

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

Output

For each test case, output a single integer — the expected total brutality modulo $$$998244353$$$.

Formally, let $$$M = 998244353$$$. 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} \pmod M$$$.

Example
Input
5
3
1 4 2
4
-5 -1 -3 -2
5
10 10 10 10 10
3
1000000000 -1000000000 0
6
3 8 -4 7 -2 5
Output
4
499122183
0
337429843
665496265
Note

In the first test case, let the gladiators be $$$A$$$, $$$B$$$, $$$C$$$ with strengths $$$1$$$, $$$4$$$, $$$2$$$ respectively. The tournament tree looks like:

Figure: The tournament tree for the first test case.

Here, $$$b$$$ denotes brutality, $$$-X$$$ on an edge means gladiator $$$X$$$ is eliminated, and the boxed numbers are the total brutality for each scenario. There are $$$6$$$ equally likely scenarios, so the expected total brutality is: $$$$$$\frac{5 + 4 + 3 + 4 + 3 + 5}{6} = \frac{24}{6} = 4.$$$$$$