$n$ 人が一列に並んでいます。$i$ 番目の人は $a_i$ 枚の硬貨を持っています。

乞食の Robin は、皆がより平等になるように手助けしたいと考えています。1 回の操作で、2 人を選び、その 2 人のお金を均等に分けます。厳密には、$1 \le i \le j \le n$ を満たす 2 つの位置 $i$ と $j$ を選び、$x=\frac{a_i+a_j}{2}$ を計算し、$a_i:=x$ および $a_j:=x$ とします。

しかし、問題が 1 つあります。硬貨は分割できません。$a_i+a_j$ が奇数の場合、Robin は 1 枚の硬貨を半分ずつに分けることができません。その場合、Robin は喜んでその 1 枚を報酬として受け取り、残りを均等に分けます。

Robin はとてもお腹がすいているので、できるだけ早く報酬を得たい（つまり、少なくとも 1 枚の硬貨を受け取りたい）と考えています。

正の整数の配列 $a_1,a_2,\ldots,a_n$ に対し、$f(a_1,a_2,\ldots,a_n)$ を、Robin が報酬を得るために行う必要がある操作の最小回数と定義します。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$）が 1 つ与えられます。

各テストケースの最初の行には、配列の長さを表す整数 $n$（$1 \le n \le 2\cdot10^5$）が 1 つ与えられます。

各テストケースの 2 行目には、各人が持つ硬貨の枚数を表す $n$ 個の整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）が与えられます。

すべてのテストケースにわたる $n$ の総和は $2\cdot10^5$ 以下であることが保証されます。

出力

各テストケースについて、与えられた配列のすべての連続部分配列に対する $f$ の値の二乗の総和を $998\,244\,353$ で割った余りを、整数 1 つとして出力してください。

入出力例

入力 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