有些人如果不通过一个复杂且有些多余的故事来包装题目，就不会感到满足。如果你是这类人，那么这道题不适合你。

给定一个非负整数序列 $a_1, a_2, \dots, a_n$。你需要找到满足 $1 \le i, j \le n$ 且 $\binom{a_i}{a_j}$ 为奇数的数对 $(i, j)$ 的数量。

注意 $\binom{n}{k}$ 是从 $n$ 个对象中选择 $k$ 个对象的方法数（不考虑顺序）。特别地，如果 $n < k$，则 $\binom{n}{k} = 0$。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 10$)。接下来是各测试用例的描述。

每个测试用例的第一行包含序列中元素的数量 $n$ ($1 \le n \le 10^6$)。

第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^6$)，即序列中的元素。

输出格式

对于每个测试用例，输出一行，包含一个整数，即该问题的答案。

样例

样例输入 1

2
3
1 5 6
3
1 1 1

样例输出 1

4
9