题目内容

安全运营中心在一次巡检中采集了 $n$ 条设备心跳报文，第 $i$ 条带有非负整数校验码 $a_i$。审计手册规定：若能选出四个下标两两不同的报文，使其校验码按位异或恰好等于当天的目标指纹 $k$，则记为一组需复核的组合。为避免重复统计，四个下标必须按 $i < j < p < q$ 计数。

请统计满足 $a_i \oplus a_j \oplus a_p \oplus a_q = k$ 的四元组个数。其中 $\oplus$ 表示按位异或：每一位上相同得 0、不同得 1。

约束：测试组数不超过 1000，单组长度满足 $4 \le n \le 1000$，所有组的 $n$ 之和不超过 4000；$k$ 与各校验码均不超过 1000000000。

输入描述

每个测试文件包含多组数据。第一行一个整数 $T$，表示组数。 每组第一行两个整数 $n$ 和 $k$，第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。 保证 $1 \le T \le 1000$，$4 \le n \le 1000$，$0 \le k, a_i \le 1000000000$，且所有组 $\sum n \le 4000$。

输出描述

输出 $T$ 行，第 $i$ 行给出第 $i$ 组满足条件的四元组个数。

样例1

输入

2
4 7
3 5 6 7
6 0
8 8 4 4 2 2

输出

1
3

说明

第一组只有一个四元组，异或 $3 \oplus 5 \oplus 6 \oplus 7 = `7`$，等于目标，答案为 1。

第二组 $k=`0`$，序列为 8,8,4,4,2,2。满足 $i<j<p<q$ 且四数异或为 0 的四元组共 3 个。

样例2

输入

1
4 1
9 9 9 9

输出

0

说明

四个 9 的异或为 0，不等于 $k=`1`$，答案为 0。

样例3

输入

1
5 0
0 0 0 0 0

输出

5

说明

$n=`5`$，$k=`0`$，全零数组任意四元组异或均为 0。四元组个数为 $\binom{5}{4}=`5`$。