染色

题目描述

选择数组中两个不同元素染红色，其余染蓝色。若红色元素和与蓝色元素和奇偶性相同，则为"史诗"方案。求史诗方案数。

输入格式

第一行 $T$。每组：第一行 $n$；第二行 $n$ 个整数。

输出格式

每组输出史诗方案数。

数据范围

$1 \leq \sum n \leq 4 \times 10^5$

样例

输入: 4 / 3 / 1 2 1 / 4 / 5 6 7 8 / ... 输出: 3 / 6 / 0 / 6