染色题目描述 你有一个包含 n 个整数的数组 a，你可以选择其中两个 不同 元素染为红色，其余元素染为蓝色。 如果 红色元素的和 和 蓝色元素的和 都是偶数或者都是奇数（即奇偶性相同），那么这种染色

题目描述

你有一个包含 n 个整数的数组 a，你可以选择其中两个 不同 元素染为红色，其余元素染为蓝色。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如果 红色元素的和 和 蓝色元素的和 都是偶数或者都是奇数（即奇偶性相同），那么这种染色方案被称为 史诗。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

你需要统计有多少种不同的染色方案可以实现 史诗（两种染色方案不同当且仅当至少一个元素在其两个染色方案中颜色不同）。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式

• 第一行是一个整数 T，表示测试点数量。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

• 接下来 T 个测试点，每个测试点包括两行：i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  • 第一行一个整数 n，表示数组的长度。
  • 第二行包含 n 个整数 a1​,a2​,…,an​，表示数组的元素。

所有测试点的 n 之和不超过 4⋅10^5。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

对于每个测试点，输出一个整数，表示有多少种不同的 史诗 染色方案。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

数据范围

对于 30% 的数据，1≤n≤4。i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

对于另外30% 的数据，1≤∑n≤700i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

对于 100% 的数据，1≤∑n≤4×10^5i6O100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例数据