CF776G Sherlock and the Encrypted Data

夏洛克发现了一段加密数据，他认为这将有助于抓住莫里亚蒂。这段加密数据包含两个整数 $l$ 和 $r$，他注意到这两个整数是十六进制表示的。 他将对从 $l$ 到 $r$ 的每个整数执行以下操作： 1. 列出该数中所有不同的数字。例如，对于 $1014_{16}$，其包含的数字为 $1, 0, 4$。 2. 对于上一步中列出的每个数字 $d$，求 $2$ 的 $d$ 次方后相加。例如上述例子中有 $sum=2^{1} + 2^{0} + 2^{4} = 19_{10}$。 3. 用初始数字和求得的 $sum$ 做按位异或操作。即初始数字与 $sum$ 按位异或，得到新数。注意异或操作在二进制下进行。 4. 检查新得到的数字是否比初始数小。 再举一个例子：对于整数 $1e$，则 $sum=2^1+2^{14}$。字母 a、b、c、d、e、f 代表十六进制数字 $10,11,12,13,14,15$。 夏洛克想统计，在区间 $[l, r]$ 内（包括 $l$ 和 $r$），经过上述操作后能变小的数的个数。现在他有 $q$ 组查询，每组查询给定不同的 $l$ 和 $r$，请你回答。

第一行包含一个整数 $q$（$1 \leq q \leq 10000$）。 接下来的 $q$ 行，每行包含两个十六进制整数 $l$ 和 $r$（$0 \leq l \leq r < 16^{15}$）。 十六进制整数使用 $0$ 到 $9$ 及小写字母 $a, b, c, d, e, f$ 表示，不含多余前导零。

输出 $q$ 行，第 $i$ 行输出第 $i$ 次查询的答案（用十进制数表示）。

对于第二组输入： $14_{16} = 20_{10}$ $sum = 2^1 + 2^4 = 18$ 因此经过操作后数字变小，可以验证区间 $[1, 1e]$ 内只有 $14_{16}$ 经过上述操作会变小。 由 ChatGPT 5 翻译