题目内容

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$ 与整数 $k$，请统计满足 $a_i \oplus a_j \oplus a_p \oplus a_q = k$ 的四元组数量。为避免重复计数，约定四个下标两两不同且按 $i < j < p < q$ 计数。

名词解释

• 按位异或（xor，记作 $\oplus$）：对每一位二进制独立计算，相同为 $0$，不同为 $1$。
• 两两不同：四个下标互不相同，不可复用同一位置的元素；本题按 $i < j < p < q$ 唯一计数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^3$）代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n, k$（$4 \le n \le 10^3, 0 \le k \le 10^9$）。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）。

所有测试中 $\sum n \le 4 \times 10^3$。

输出描述

输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案（满足条件的四元组数量）。

样例1

输入

2
4 0
1 2 1 2
5 2
1 1 2 2 3

输出

1
2

说明

第一组数据 $n = 4$，$k = 0$，数组为 $[1, 2, 1, 2]$。唯一可选四元组下标 $(1, 2, 3, 4)$，异或和 $1 \oplus 2 \oplus 1 \oplus 2 = 0$，满足条件，答案为 $1$。

第二组数据 $n = 5$，$k = 2$，数组为 $[1, 1, 2, 2, 3]$。满足条件的四元组下标为 $(1, 3, 4, 5)$：$1 \oplus 2 \oplus 2 \oplus 3 = 2$；$(2, 3, 4, 5)$：$1 \oplus 2 \oplus 2 \oplus 3 = 2$。共 $2$ 组，答案为 $2$。