区间异或

题目描述

给出一个正整数序列$a_{1}$,$a_{2}$,$\cdots$,$a_{n}$。求有多少个区间$[l,r]$（$1 \leq l \leq r \leq n$）的异或和不小于给定的正整数$K$，即求满足下列条件的区间$[l,r]$总数：

$$a_{l} \oplus a_{l+1} \oplus a_{l+2} \oplus \cdots \oplus a_{r-1} \oplus a_{r} \geq K $$

其中$\oplus$表示异或。

输入格式

本题的每个测试点包含多组测试数据。

第一行，一个整数$T$，表示数据组数。

• 第$2T$行包含两个整数$n$，$K$，$n$为正整数序列中元素个数，$K$的含义如上所述。
• 第$2T+1$行包含$n$个正整数$a_{1}$,$a_{2}$,$\cdots$,$a_{n}$，即正整数序列中的元素。

输出格式

输出$T$行，每行一个正整数表示答案。

数据范围与提示

• 对于$20\%$的数据，$n < 2000$；
• 对于$100\%$的数据，$1 < T < 5$，$1 \leq n \leq 10^{6}$，$0 \leq K \leq 10^{9}$，$1 \leq a_{i} \leq 10^{9}$。数据有一定梯度。

样例

3
3 1	
1 2 3
3 2
1 2 3
3 3
1 2 3

5
3
2