题目描述

瓜瓜认为正整数 $x$ 是好的，当且仅当正整数 $x$ 在十进制下任意相邻两个数位的异或都是 $w$，若不足两位则不是好数。

比如当 $w=3$ 时，$56$ 是好数，因为 $5 \oplus 6 = 3$。

比如对于三位数 $\overline{abc}$，则需要满足 $a \oplus b = b \oplus c = w$。

瓜瓜想知道在区间 $[l, r]$ 中，有多少个好数？

输入描述

第一行有一个整数 $T(1 \leqslant T \leqslant 5000)$，表示有 $T$ 组样例。

接下来每行有三个正整数 $l, r, w$，其中 $1 \leqslant l \leqslant r \leqslant 10^{17}, 0 \leqslant w \leqslant 15$。

提示：$\texttt{int}$ 类型最大值是 $2^{31} - 1 < 10^{17}$，更大的范围可以使用 $\texttt{long long}$。

输出描述

输出共 $T$ 行，每行有一个整数，表示你的答案。

样例

5
1 9 2
13 13 2
1 15 2
12 45 3
11 11 0

0
1
1
3
1

提示

在第 $4$ 个测试点中，区间 $[12, 45]$ 在 $w=3$ 下的好数有 $12, 21, 30$。

异或：对于 $c = a \oplus b$，若 $a$ 和 $b$ 二进制下对应 bit 位不同，则为 $1$，否则为 $0$。在 C 语言中，用 $\texttt{a \^ \ b}$ 来表示。

比如 $5 \oplus 6 = 101_2 \oplus 110_2 = 011_2 = 3$。