Hay $n$ personas de pie en una fila. La $i$-ésima persona tiene $a_i$ monedas.

El mendigo Robin quiere ayudar a que todos sean más iguales. En una operación, elige a dos personas y reparte su dinero por igual entre ellas. Formalmente, elige dos posiciones $i$ y $j$ tales que $1 \le i \le j \le n$, calcula $x = \frac{a_i+a_j}{2}$ y después establece $a_i := x$ y $a_j := x$.

Pero hay un problema: las monedas son indivisibles. Si $a_i+a_j$ es impar, Robin no puede dividir una moneda en dos mitades. En ese caso, Robin se queda encantado con esa moneda como salario y reparte el resto por igual.

Robin tiene mucha hambre, así que quiere ganar su salario (es decir, quedarse con al menos una moneda) lo antes posible.

Para un arreglo $a_1,a_2,\ldots,a_n$ de enteros positivos, definimos $f(a_1,a_2,\ldots,a_n)$ como el número mínimo de operaciones que Robin necesita realizar para ganar su salario. Si Robin nunca puede ganar su salario, entonces $f(a_1,a_2,\ldots,a_n)=0$.

Se te da un arreglo $a_1,a_2,\ldots,a_n$. Tu tarea es calcular

$$ \sum_{l=1}^{n}\sum_{r=l}^{n} f(a_l,\ldots,a_r)^2 $$

módulo $998\,244\,353$.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 10^4$): el número de casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($1 \le n \le 2\cdot 10^5$): la longitud del arreglo.

La segunda línea de cada caso de prueba contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$): las cantidades de monedas que tienen las personas.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2\cdot 10^5$.

Salida

Para cada caso de prueba, imprime un único entero: la suma de los cuadrados de los valores de $f$ para todos los subarreglos del arreglo dado, módulo $998\,244\,353$.

Ejemplos

Entrada 1

4
3
2 18 2
10
1 2 3 4 5 6 7 8 9 10
5
20 36 100 36 20
2
1000000000 999999999

Salida 1

25
45
174
1