单点时限: 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)$
每组数据输出一行结果
2 3 1 2 3 3 1 1 1
5 9