English · Original
Chinese · Translation
Formal · Original
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_.
## Input
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.
## Output
Output _q_ lines, _i_\-th line contains answer to the _i_\-th query (in decimal notation).
[samples]
## Note
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.
Sherlock 找到了一段他认为对抓住 Moriarty 有用的加密数据。该加密数据由两个整数 $l$ 和 $r$ 组成。他注意到这些整数是以十六进制形式表示的。
他取从 $l$ 到 $r$（包含两端）的每个整数，并执行以下操作：
另一个例子：对于整数 _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 < 16^{15}$）。
十六进制整数由数字 $0$ 到 $9$ 和/或小写英文字母 _a_, _b_, _c_, _d_, _e_, _f_ 组成。
十六进制整数不包含前导零。
请输出 $q$ 行，第 $i$ 行包含第 $i$ 个查询的答案（以十进制表示）。
对于第二个输入：
$14_{16} = 20_{10}$
$sum = 21 + 24 = 18$
因此，该数减小了。我们可以验证，在范围 $1$ 到 $1e$ 中，只有这一个数会减小。
## Input
第一行包含整数 $q$（$1 ≤ q ≤ 10000$）。接下来的 $q$ 行，每行包含两个十六进制整数 $l$ 和 $r$（$0 ≤ l ≤ r < 16^{15}$）。十六进制整数由数字 $0$ 到 $9$ 和/或小写英文字母 _a_, _b_, _c_, _d_, _e_, _f_ 组成。十六进制整数不包含前导零。
## Output
请输出 $q$ 行，第 $i$ 行包含第 $i$ 个查询的答案（以十进制表示）。
[samples]
## Note
对于第二个输入：
$14_{16} = 20_{10}$
$sum = 21 + 24 = 18$
因此，该数减小了。我们可以验证，在范围 $1$ 到 $1e$ 中，只有这一个数会减小。
**Definitions**
Let $ q \in \mathbb{Z} $ be the number of queries.
For each query $ i \in \{1, \dots, q\} $, let $ l_i, r_i \in \mathbb{Z} $ be the endpoints of a hexadecimal range, interpreted as base-16 integers with $ 0 \le l_i \le r_i < 16^{15} $.
Define a function $ f: \mathbb{Z}_{\ge 0} \to \mathbb{Z}_{\ge 0} $ such that for any integer $ n $, $ f(n) $ is the sum of the decimal values of its hexadecimal digits.
That is, if $ n $ has hexadecimal representation $ d_k d_{k-1} \dots d_1 d_0 $, where each $ d_j \in \{0,1,\dots,9,a,b,c,d,e,f\} $ maps to $ \{0,1,\dots,15\} $, then:
$$
f(n) = \sum_{j=0}^{k} \text{val}(d_j), \quad \text{where } \text{val}(d) =
\begin{cases}
d & \text{if } d \in \{0,\dots,9\} \\
10 + (d - 'a') & \text{if } d \in \{a,b,c,d,e,f\}
\end{cases}
$$
**Constraints**
1. $ 1 \le q \le 10000 $
2. For each query $ i $: $ 0 \le l_i \le r_i < 16^{15} $
3. Hexadecimal inputs contain no leading zeros and use only digits `0-9` and lowercase letters `a-f`.
**Objective**
For each query $ i $, compute the count of integers $ n \in [l_i, r_i] $ such that $ f(n) < n $.
API Response (JSON)
{
"problem": {
"name": "G. Sherlock and the Encrypted Data",
"description": {
"content": "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 fo",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF776G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 fo...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Sherlock 找到了一段他认为对抓住 Moriarty 有用的加密数据。该加密数据由两个整数 $l$ 和 $r$ 组成。他注意到这些整数是以十六进制形式表示的。\n\n他取从 $l$ 到 $r$（包含两端）的每个整数，并执行以下操作：\n\n另一个例子：对于整数 _1e_，其交错和为 $sum = 21 + 214$。字母 _a_, _b_, _c_, _d_, _e_, _f_ 分别表示十六进制数字...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ q \\in \\mathbb{Z} $ be the number of queries. \nFor each query $ i \\in \\{1, \\dots, q\\} $, let $ l_i, r_i \\in \\mathbb{Z} $ be the endpoints of a hexadecimal range, interpreted as...",
"is_translate": false,
"language": "Formal"
}
]
}