时间限制： 2.0 秒

空间限制： 256 MB

题目描述

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

输入格式

从标准输入读入数据。

第一行为数据组数 $T~(1\le T\le 10)$。

每组数据第一行为 $n~(1\le n\le 10^5)$，接下来一行有 $n$ 个数 $a_{1} , a_{2} , \ldots , a_{n},~(0\le a_i\le 10^5)$。

输出格式

输出到标准输出。

每组数据输出一行一个整数表示结果。

2
3
1 2 3
3
1 1 1

5
9