Before her final sortie, Chtholly asks Willem three questions.

The third is this: when the end finally comes, who will remain to witness it?

Willem cannot answer her directly. Instead, he draws a circle on the board, calling it the ring of all things, and writes down $n$ labeled integers $a_1,a_2,\ldots,a_n$. Every possible order around the ring describes a different way in which the world might reach its end.

Consider a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$. Place the corresponding numbers on a circle in this order. The weight of the resulting circular arrangement is

$$ \prod_{i=1}^{n}(a_{p_i}+a_{p_{i+1}}), $$

where $p_{n+1}=p_1$.

Two permutations describe the same circular arrangement if one can be obtained from the other by a cyclic shift. Reversing an arrangement does not make it the same arrangement; in other words, reflected arrangements are considered different unless they also coincide after a cyclic shift.

Find the sum of the weights of all distinct circular arrangements. Since the answer may be large, output it modulo $998\,244\,353$.

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 one integer $n$ ($3 \le n \le 2\cdot 10^5$) — the number of labeled integers.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \lt 998\,244\,353$).

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

Output

For each test case, output one integer — the sum of the weights of all distinct circular arrangements, modulo $998\,244\,353$.

Note

In the first test case, there are two distinct circular arrangements. They can be represented by the permutations $[1,2,3]$ and $[1,3,2]$. Both have weight

$$ (1+2)(2+3)(3+1)=60, $$

so the answer is $120$.

In the second test case, an arrangement has nonzero weight only if zeros and ones alternate around the circle. There are

$$ \frac{2\cdot3!\cdot3!}{6}=12 $$

such circular arrangements: the factor $2$ chooses whether a linear representative starts with a zero or a one, and division by $6$ identifies cyclic shifts. Each arrangement has weight $1$. All other arrangements have weight $0$, so the answer is $12$.