← 返回题目列表

Codeforces · 776/G

G. 夏洛克和加密数据

中文机器翻译题面 查看原题

夏洛克发现了一段加密数据,他认为这对抓住莫里亚蒂很有用。加密数据由两个整数l和r组成。他注意到这些整数是十六进制形式。

他取出从 l 到 r 的每个整数,并执行以下操作:

1. 他列出了给定数字中存在的不同数字。例如:对于 101416,他将数字列出为 1、 0、 4。
2. 然后,他将上述步骤中列出的每个数字各自的 2 的幂相加。就像上面的例子 sum = 21 + 20 + 24 = 1910。
3. 他通过对初始数和总和进行按位异或来更改初始数。示例:$$1014_{16} \oplus 19_{10} = 4116_{10} \oplus 19_{10} = 4103_{10}$$。请注意,异或是以二进制表示法完成的。

再举一个例子:对于整数 1e,总和为 sum = 21 + 214。字母 a、b、c、d、e、f 分别表示十六进制数字 10、11、12、13、14、15。

Sherlock 想要计算从 l 到 r(包括两者)范围内的数字,这些数字在应用上述四个步骤后会减少。他希望你回答他对不同 l 和 r 的 q 查询。

输入

第一行包含整数 q (1 ≤ q ≤ 10000)。

接下来的 q 行包含两个十六进制整数 l 和 r (0 ≤ l ≤ r < 1615)。

十六进制整数使用 0 到 9 的数字和/或小写英文字母 a、b、c、d、e、f 书写。

十六进制整数不包含额外的前导零。

输出

输出 q 行,第 i 行包含第 i 个查询的答案(以十进制表示)。

示例

输入 #1

1
1014 1014

输出 #1

1

输入 #2

2
1 1e
1 f

输出 #2

1
0

输入 #3

2
1 abc
d0e fe23

输出 #3

412
28464

注意

对于第二个输入,

1416 = 2010

总和 = 21 + 24 = 18

$$20 \oplus 18 = 6$$

因此,它减少了。并且,我们可以验证它是 1 到 1e 范围内唯一减少的数字。