$n$명의 사람이 일렬로 서 있다. $i$번째 사람은 동전 $a_i$개를 가지고 있다.

거지 Robin은 모두가 더 평등해지도록 돕고 싶다. 한 번의 연산에서 그는 두 사람을 골라 그들의 돈을 둘에게 똑같이 나누어 준다. 정확히 말하면, $1 \le i \le j \le n$인 두 위치 $i$와 $j$를 고르고, $x = \frac{a_i+a_j}{2}$를 계산한 다음 $a_i := x$, $a_j := x$로 설정한다.

그런데 한 가지 문제가 있다. 동전은 쪼갤 수 없다. $a_i+a_j$가 홀수이면 Robin은 동전 하나를 두 조각으로 나눌 수 없다. 이 경우 Robin은 기꺼이 그 동전 하나를 자신의 보수로 가져가고, 나머지를 똑같이 나누어 준다.

Robin은 매우 배가 고프므로 가능한 한 빨리 보수를 받고 싶다(즉, 동전을 적어도 하나 가져가고 싶다).

양의 정수 배열 $a_1,a_2,\ldots,a_n$에 대해, Robin이 보수를 받기 위해 수행해야 하는 최소 연산 횟수를 $f(a_1,a_2,\ldots,a_n)$으로 정의한다. Robin이 보수를 절대로 받을 수 없다면 $f(a_1,a_2,\ldots,a_n)=0$이다.

배열 $a_1,a_2,\ldots,a_n$이 주어진다. 다음 값을 계산하여

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

$998\,244\,353$으로 나눈 나머지를 구하여라.

입력

첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 10^4$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에 배열의 길이를 나타내는 정수 $n$ ($1 \le n \le 2\cdot 10^5$)이 주어진다.

각 테스트 케이스의 두 번째 줄에 사람들이 가진 동전의 개수를 나타내는 $n$개의 정수 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$)이 주어진다.

모든 테스트 케이스에 대한 $n$의 합은 $2\cdot 10^5$를 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 주어진 배열의 모든 부분 배열에 대한 $f$ 값의 제곱의 합을 $998\,244\,353$으로 나눈 나머지를 나타내는 정수 하나를 출력하여라.

예제

입력 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

출력 1

25
45
174
1