XOR 三元组的数目

题目背景

Rick在刷力扣的时候遇到了一道有趣的题目：给定一个长度为 n 的整数数组，这个数组恰好是 1 到 n 这 n 个数的某个排列。从数组中任选三个元素（下标可以重复），计算它们的异或（XOR）值。问：一共能得到多少个不同的 XOR 值？

Rick隐隐感到答案和数组的具体排列顺序无关，而只和长度 n 有关。你能证明这一点，并帮他快速计算出答案吗？

题目描述

给定 t 组测试数据。每组数据包含一个长度为 n 的整数数组 a₁, a₂, …, aₙ，保证这个数组是 1 到 n 这 n 个数的一个排列。

你可以选择任意三个下标 i, j, k（1 ≤ i, j, k ≤ n，下标可以重复），得到一个值：

S = aᵢ ⊕ aⱼ ⊕ aₖ

其中 ⊕ 表示按位异或（XOR）运算。

请你求出：所有可能的 S 值中，不同值的个数。

输入格式

第一行一个整数 t（1 ≤ t ≤ 10⁴），表示测试数据组数。

接下来每组数据：

• 第一行一个整数 n（1 ≤ n ≤ 10⁵），表示数组长度。
• 第二行 n 个整数 a₁, a₂, …, aₙ，保证这 n 个数是 1 到 n 的一个排列（即恰好包含 1 到 n 各一次）。

保证所有测试数据的 n 之和不超过 3 × 10⁵。

输出格式

对于每组数据，输出一行一个整数，表示不同 XOR 三元组值的个数。

样例

2
2
1 2
3
3 1 2

2
4

3
4
2 4 1 3
7
5 3 7 1 2 6 4
8
8 5 3 1 7 2 6 4

8
8
16

数据范围

• 1 ≤ t ≤ 10⁴
• 1 ≤ n ≤ 10⁵
• 1 ≤ aᵢ ≤ n，且数组是 1 到 n 的排列
• Σn ≤ 3 × 10⁵