给定三个二进制表示的非负整数 $L, R$ 和 $X$。求整数序列 $(L \oplus X, (L + 1) \oplus X, \dots, R \oplus X)$（长度为 $R - L + 1$）的逆序对数量，并以二进制形式输出。

在此，$\oplus$ 表示按位异或运算。

共有 $T$ 组测试数据；请解决每一组数据。

逆序对的定义

长度为 $M$ 的序列 $B = (B_1, B_2, \dots, B_M)$ 的逆序对数量，是指满足 $1 \le i < j \le M$ 且 $B_i > B_j$ 的整数对 $(i, j)$ 的个数。

输入格式

输入通过标准输入按以下格式给出：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例的格式如下：

$L \ R \ X$

• $1 \le T \le 2 \times 10^5$
• $0 \le L \le R < 2^{2 \times 10^5}$
• $0 \le X < 2^{2 \times 10^5}$
• $L, R$ 和 $X$ 以二进制表示，且不含前导零（$0$ 被视为一位整数）。
• 所有测试用例中 $R$ 的二进制表示的总位数不超过 $2 \times 10^5$。
• 所有测试用例中 $X$ 的二进制表示的总位数不超过 $2 \times 10^5$。
• 所有输入值均为整数。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案，以二进制形式表示。

样例

样例输入 1

3
101 1000 10
1101 10111010 0
1000110 1110011011101 100011110010

样例输出 1

10
0
11100100001101111010100

说明

在第一个测试用例中，$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$。