3300. 奇数统计

单点时限: 2.0 sec

内存限制: 256 MB

章鱼王有 $n$ 个数,章鱼王从中选出一个数 $A$ 记录在纸上,然后再选出一个数 $B$ 记录在纸上,共有 $n^2$ 种不同取法,章鱼王想要知道这其中有多少种不同取法可以令 $C_A^B$(从 $A$ 个球种取出 $B$ 个球的方案数)为奇数。

输入格式

第一行为数据组数 $T(T\leq 10)$

每组数据第一行为 $n(1\leq n\leq 100000)$,接下来一行有 $n$ 个数 $a_1,a_2,\cdots,a_n(0\leq a_i\leq 100000)$

输出格式

每组数据输出一行结果

样例

Input
2
3
1 2 3
3
1 1 1
Output
5
9

54 人解决,122 人已尝试。

74 份提交通过,共有 498 份提交。

5.6 EMB 奖励。

创建: 3 年,2 月前.

修改: 3 年前.

最后提交: 2 天,5 小时前.

来源: 2017 高可信软件夏令营上机测试

题目标签