给定非负整数 $L, R, X$，以二进制形式给出。请用二进制输出长度为 $R-L+1$ 的整数序列 $(L \oplus X, (L+1)\oplus X, \dots, R\oplus X)$ 的逆序对数。

其中，$\oplus$ 表示按位异或操作。

一共有 $T$ 组测试数据，分别求出每组的答案。

逆序对数的定义如下：对于数列 $B=(B_1,B_2,\dots,B_M)$，逆序对是满足 $1 \leq i < j \leq M$ 且 $B_i > B_j$ 的整数对的个数。

按位异或的定义如下：对于非负整数 $A,B$，它们的异或 $A \oplus B$ 是指将 $A,B$ 按二进制表示后，每一位如果 $A$ 或 $B$ 在该位上有且只有一个是 $1$，则结果该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$，二进制表示为：$011 \oplus 101 = 110$。

输入以如下格式从标准输入给出。

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每组测试数据的格式如下：

$L$ $R$ $X$

输出共 $T$ 行。第 $i$ 行输出第 $i$ 个测试数据的答案。

部分分

对于满足额外约束 $T \leq 3000, R < 2^{30}, X < 2^{30}$ 的数据集，若答案正确可获得 $10$ 分。

样例解释 1

对于第 $1$ 个测试数据，将 $L,R,X$ 转为十进制分别为 $L=5, R=8, X=2$。$(5\oplus 2, 6\oplus 2, 7\oplus 2, 8\oplus 2)=(7,4,5,10)$，所要求的逆序对数为 $2$。

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $0 \leq L \leq R < 2^{2\times 10^5}$
• $0 \leq X < 2^{2\times 10^5}$
• 所有输入均为整数
• $T$ 用十进制给出
• $L, R, X$ 用二进制给出，且不含前导多余 $0$（$0$ 例外，视为一位整数）
• 单个输入文件中 $R$ 的所有二进制位数之和不超过 $2\times 10^5$
• 单个输入文件中 $X$ 的所有二进制位数之和不超过 $2\times 10^5$

由 ChatGPT 5 翻译