{"raw_statement":[{"iden":"statement","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 form.\n\nHe takes each of the integers from _l_ to _r_, and performs the following operations:\n\n1.  He lists the distinct digits present in the given number. For example: for 101416, he lists the digits as 1, 0, 4.\n2.  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.\n3.  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.\n\nOne 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.\n\nSherlock 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_."},{"iden":"input","content":"First line contains the integer _q_ (1 ≤ _q_ ≤ 10000).\n\nEach of the next _q_ lines contain two hexadecimal integers _l_ and _r_ (0 ≤ _l_ ≤ _r_ < 1615).\n\nThe hexadecimal integers are written using digits from 0 to 9 and/or lowercase English letters _a_, _b_, _c_, _d_, _e_, _f_.\n\nThe hexadecimal integers do not contain extra leading zeros."},{"iden":"output","content":"Output _q_ lines, _i_\\-th line contains answer to the _i_\\-th query (in decimal notation)."},{"iden":"examples","content":"Input\n\n1\n1014 1014\n\nOutput\n\n1\n\nInput\n\n2\n1 1e\n1 f\n\nOutput\n\n1\n0\n\nInput\n\n2\n1 abc\nd0e fe23\n\nOutput\n\n412\n28464"},{"iden":"note","content":"For the second input,\n\n1416 = 2010\n\n_sum_ = 21 + 24 = 18\n\nThus, it reduces. And, we can verify that it is the only number in range 1 to 1_e_ that reduces."}],"translated_statement":[{"iden":"statement","content":"Sherlock 找到了一段他认为对抓住 Moriarty 有用的加密数据。该加密数据由两个整数 $l$ 和 $r$ 组成。他注意到这些整数是以十六进制形式表示的。\n\n他取从 $l$ 到 $r$（包含两端）的每个整数，并执行以下操作：\n\n另一个例子：对于整数 _1e_，其交错和为 $sum = 21 + 214$。字母 _a_, _b_, _c_, _d_, _e_, _f_ 分别表示十六进制数字 $10$, $11$, $12$, $13$, $14$, $15$。\n\nSherlock 希望统计在范围 $l$ 到 $r$（包含两端）内，经过上述四个步骤后数值减小的数的个数。他需要你回答他关于不同 $l$ 和 $r$ 的 $q$ 个查询。\n\n第一行包含整数 $q$（$1 ≤ q ≤ 10000$）。\n\n接下来的 $q$ 行，每行包含两个十六进制整数 $l$ 和 $r$（$0 ≤ l ≤ r < 16^{15}$）。\n\n十六进制整数由数字 $0$ 到 $9$ 和/或小写英文字母 _a_, _b_, _c_, _d_, _e_, _f_ 组成。\n\n十六进制整数不包含前导零。\n\n请输出 $q$ 行，第 $i$ 行包含第 $i$ 个查询的答案（以十进制表示）。\n\n对于第二个输入：\n\n$14_{16} = 20_{10}$\n\n$sum = 21 + 24 = 18$\n\n \n\n因此，该数减小了。我们可以验证，在范围 $1$ 到 $1e$ 中，只有这一个数会减小。"},{"iden":"input","content":"第一行包含整数 $q$（$1 ≤ q ≤ 10000$）。接下来的 $q$ 行，每行包含两个十六进制整数 $l$ 和 $r$（$0 ≤ l ≤ r < 16^{15}$）。十六进制整数由数字 $0$ 到 $9$ 和/或小写英文字母 _a_, _b_, _c_, _d_, _e_, _f_ 组成。十六进制整数不包含前导零。"},{"iden":"output","content":"请输出 $q$ 行，第 $i$ 行包含第 $i$ 个查询的答案（以十进制表示）。"},{"iden":"examples","content":"输入1\n1014\n1014\n输出1\n\n输入2\n1\n1e\n1\nf\n输出1\n0\n\n输入2\n1\nabcd0e\nfe23\n输出41228464"},{"iden":"note","content":"对于第二个输入：\n$14_{16} = 20_{10}$\n$sum = 21 + 24 = 18$\n因此，该数减小了。我们可以验证，在范围 $1$ 到 $1e$ 中，只有这一个数会减小。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 base-16 integers with $ 0 \\le l_i \\le r_i < 16^{15} $.  \n\nDefine 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.  \nThat 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:  \n$$\nf(n) = \\sum_{j=0}^{k} \\text{val}(d_j), \\quad \\text{where } \\text{val}(d) = \n\\begin{cases}\nd & \\text{if } d \\in \\{0,\\dots,9\\} \\\\\n10 + (d - 'a') & \\text{if } d \\in \\{a,b,c,d,e,f\\}\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\le q \\le 10000 $  \n2. For each query $ i $: $ 0 \\le l_i \\le r_i < 16^{15} $  \n3. Hexadecimal inputs contain no leading zeros and use only digits `0-9` and lowercase letters `a-f`.  \n\n**Objective**  \nFor each query $ i $, compute the count of integers $ n \\in [l_i, r_i] $ such that $ f(n) < n $.","simple_statement":null,"has_page_source":false}