题目描述

你有一个包含 $n$ 个整数的数组 $a$，你可以选择其中两个 不同 元素染为红色，其余元素染为蓝色。

如果 红色元素的和 和 蓝色元素的和 都是偶数或者都是奇数（即奇偶性相同），那么这种染色方案被称为 史诗。

你需要统计有多少种不同的染色方案可以实现 史诗（两种染色方案不同当且仅当至少一个元素在其两个染色方案中颜色不同）。

输入格式

• 第一行是一个整数 $T$，表示测试点数量。

• 接下来 $T$ 个测试点，每个测试点包括两行：

  • 第一行一个整数 $n$，表示数组的长度。
  • 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。

所有测试点的 $n$ 之和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试点，输出一个整数，表示有多少种不同的 史诗 染色方案。

4
3
1 2 1
4
5 6 7 8
5
1 9 11 13 15
4
2 4 6 8

3
6
0
6

数据范围

对于 $30\%$ 的数据，$1\le n\le 4$。

对于另外 $30\%$ 的数据，$1\le \sum n \le 700$

对于 $100\%$ 的数据，$1\le \sum n \le 4\times 10^5$