夏洛克发现了一段加密数据,他认为这对抓住莫里亚蒂很有用。加密数据由两个整数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 范围内唯一减少的数字。