CF776G.Sherlock and the Encrypted Data

Sherlock found a piece of encrypted data which he thinks will be useful to catch Moriarty. The encrypted data consists of two integer l and r. He noticed that these integers were in hexadecimal form.

He takes each of the integers from l to r, and performs the following operations:

1. He lists the distinct digits present in the given number. For example: for 101416, he lists the digits as 1, 0, 4.
2. Then he sums respective powers of two for each digit listed in the step above. Like in the above example sum = 21 + 20 + 24 = 1910.
3. He changes the initial number by applying bitwise xor of the initial number and the sum. Example: . Note that xor is done in binary notation.

One more example: for integer 1e the sum is sum = 21 + 214. Letters a, b, c, d, e, f denote hexadecimal digits 10, 11, 12, 13, 14, 15, respertively.

Sherlock wants to count the numbers in the range from l to r (both inclusive) which decrease on application of the above four steps. He wants you to answer his q queries for different l and r.

夏洛克发现了一段加密数据，他认为这段数据对抓捕莫里亚蒂很有帮助。该加密数据包含两个整数 $l$ 和 $r$，他注意到这两个整数是以十六进制形式给出的。

他对区间 $[l, r]$ 内的每个整数执行如下操作：

1. 列出该数中出现的所有不同数字。例如：对 $1014_{16}$，他列出的数字为 $1,\,0,\,4$。
2. 对步骤 1 中列出的每个数字，计算对应的 $2$ 的幂次并求和。例如在上例中，$\text{sum} = 2^1 + 2^0 + 2^4 = 19_{10}$。
3. 将原数与该和进行按位异或（xor） 运算，从而得到新数。例如：。注意：异或运算是基于二进制表示进行的。

再举一例：对整数 $1e_{16}$，其各位数字为 $1$ 和 $e$（即十进制的 $14$），因此 $\text{sum} = 2^1 + 2^{14}$。其中字母 $a,b,c,d,e,f$ 分别表示十六进制数字 $10,11,12,13,14,15$。

夏洛克希望统计在区间 $[l, r]$（含端点）中有多少个数，在执行上述三步操作后数值变小了。他希望你回答 $q$ 个查询，每个查询给出不同的 $l$ 和 $r$。

First line contains the integer q (1 ≤ q ≤ 10000).

Each of the next q lines contain two hexadecimal integers l and r (0 ≤ l ≤ r < 1615).

The hexadecimal integers are written using digits from 0 to 9 and/or lowercase English letters a, b, c, d, e, f.

The hexadecimal integers do not contain extra leading zeros.

第一行包含一个整数 $q$（$1 \le q \le 10000$）。

接下来的 $q$ 行，每行包含两个十六进制整数 $l$ 和 $r$（$0 \le l \le r < 16^{15}$）。

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

十六进制整数不包含多余的前导零。

Output q lines, i-th line contains answer to the i-th query (in decimal notation).

输出 $q$ 行，第 $i$ 行包含第 $i$ 个查询的答案（以十进制表示）。

For the second input,

1416 = 2010

sum = 21 + 24 = 18

Thus, it reduces. And, we can verify that it is the only number in range 1 to 1_e_ that reduces.

对于第二个输入，

1416 = 2010

sum = 21 + 24 = 18

因此，它会约简。并且，我们可以验证：在 1 到 1_e 的范围内，它是唯一一个会约简的数。