乞丐 Robin

输入文件：标准输入

输出文件：标准输出

时间限制：1 秒

内存限制：1024 MB

有 (n) 个人排成一行。第 (i) 个人有 (a_i) 枚硬币。

乞丐 Robin 想帮助大家变得更加平等。每次操作中，他选择两个人，并将他们的钱平均分配。形式化地说，他选择两个位置 (i) 和 (j)，满足 (1 \le i \le j \le n)，计算 (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)，定义 (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)），表示测试用例数。

每个测试用例的第一行包含一个整数 (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