Dany jest ciąg o długości $n$. Xiaoming wykona na nim $n-1$ operacji: w każdym kroku wybiera losowo (z równym prawdopodobieństwem) parę sąsiednich liczb i zastępuje je różnicą: liczba po lewej stronie minus liczba po prawej stronie. Po pierwszej operacji ciąg ma długość $n-1$, po kolejnej $n-2$ i tak dalej.

Xiaoming chce wiedzieć, jaka jest wartość oczekiwana liczby, która pozostanie po wykonaniu $n-1$ operacji. Pomóż mu. Jeśli wynik wynosi $p/q$, należy wyprowadzić wartość $p \times q^{998244351} \pmod{998244353}$. Zadanie zawiera wiele zestawów danych.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$, oznaczającą liczbę zapytań. Następnie następuje $T$ zestawów danych. Każdy zestaw składa się z: Pierwsza linia zawiera liczbę całkowitą $n$, oznaczającą długość ciągu. Druga linia zawiera $n$ liczb całkowitych $a_i$, oznaczających elementy ciągu.

Wyjście

Dla każdego zapytania wyprowadź w osobnej linii wynik odpowiadający wartości oczekiwanej.

Przykład

Wejście 1

2
2
2 1
3
3 2 1

Wyjście 1

1
1

Uwagi

Dla drugiego zapytania, jeśli najpierw wykonamy operację na dwóch pierwszych liczbach, wynik wynosi $(3 - 2) - 1 = 0$. Jeśli najpierw wykonamy operację na dwóch ostatnich liczbach, wynik wynosi $3 - (2 - 1) = 2$. Zatem wartość oczekiwana wynosi $2/2 = 1$.

Przykład 2

Zobacz pliki aminusb/aminusb2.in oraz aminusb/aminusb2.ans w katalogu zawodnika.

Podzadania

Dla 100% danych wejściowych zachodzi $T = 5$, $1 \le n \le 10^5$, $0 \le a_i < 998244353$.