There is a sequence of length $n$. Xiaoming will perform $n-1$ operations on it: each time, he chooses a pair of adjacent numbers with equal probability and replaces them with the result of the left number minus the right number. After the first operation, the sequence becomes length $n-1$, after another operation it becomes length $n-2$, and so on.

Xiaoming wants to know the expected value of the final remaining number after $n-1$ operations. Please help him. If the answer is $p/q$, you only need to output the result of $p \times q^{998244351} \pmod{998244353}$.

There are multiple queries in this problem.

Input

The first line contains a positive integer $T$, representing the number of queries.

For each of the $T$ queries, the first line contains a positive integer $n$, representing the length of the array.

The next line contains $n$ integers $a_i$, representing the sequence.

Output

Output $T$ lines, each containing one number, representing the answer for the corresponding query.

Examples

Input 1

2
2
2 1
3
3 2 1

Output 1

1
1

Note 1

For the second query, if the first two numbers are operated on first, the result is $(3 - 2) - 1 = 0$. If the last two numbers are operated on first, the result is $3 - (2 - 1) = 2$. Therefore, the expectation is $2/2 = 1$.

Input 2

4
4
1 2 3 4
5
1 2 3 4 5
6
1 2 3 4 5 6
7
1 2 3 4 5 6 7

Output 2

998244351
0
2
0

Subtasks

For 100% of the data, it is guaranteed that $T = 5$, $1 \le n \le 10^5$, and $0 \le a_i < 998244353$.