{"raw_statement":[{"iden":"statement","content":"Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and is now present in the Ministry of Magic in the office of Dolorous Umbridge, Harry's former Defense Against the Dark Arts teacher.\n\nHarry, Ron and Hermione are infiltrating the Ministry. Upon reaching Umbridge's office, they observed a code lock with a puzzle asking them to calculate count of magic numbers between two integers _l_ and _r_ (both inclusive).\n\nHarry remembered from his detention time with Umbridge that she defined a magic number as a number which when converted to a given base _b_, all the digits from 0 to _b_ - 1 appear even number of times in its representation without any leading zeros.\n\nYou have to answer _q_ queries to unlock the office. Each query has three integers _b__i_, _l__i_ and _r__i_, the base and the range for which you have to find the count of magic numbers."},{"iden":"input","content":"First line of input contains _q_ (1 ≤ _q_ ≤ 105) — number of queries.\n\nEach of the next _q_ lines contain three space separated integers _b__i_, _l__i_, _r__i_ (2 ≤ _b__i_ ≤ 10, 1 ≤ _l__i_ ≤ _r__i_ ≤ 1018)."},{"iden":"output","content":"You have to output _q_ lines, each containing a single integer, the answer to the corresponding query."},{"iden":"examples","content":"Input\n\n2\n2 4 9\n3 1 10\n\nOutput\n\n1\n2\n\nInput\n\n2\n2 1 100\n5 1 100\n\nOutput\n\n21\n4"},{"iden":"note","content":"In sample test case 1, for first query, when we convert numbers 4 to 9 into base 2, we get:\n\n*   4 = 1002,\n*   5 = 1012,\n*   6 = 1102,\n*   7 = 1112,\n*   8 = 10002,\n*   9 = 10012.\n\nOut of these, only base 2 representation of 9 has even number of 1 and 0. Thus, the answer is 1."}],"translated_statement":[{"iden":"statement","content":"哈利从邓布利多那里得知，萨拉查·斯莱特林的挂坠是一个魂器。这个挂坠此前位于格里莫广场12号，即小天狼星·布莱克母亲的家。它被从那里偷走，现在位于魔法部多洛雷斯·乌姆里奇的办公室内，而乌姆里奇正是哈利的前黑魔法防御术老师。\n\n哈利、罗恩和赫敏潜入了魔法部。当他们到达乌姆里奇的办公室时，发现了一个密码锁，上面有一个谜题，要求他们计算在两个整数 #cf_span[l] 和 #cf_span[r]（包含两端）之间有多少个“魔法数”。\n\n哈利回忆起在乌姆里奇那里接受处罚时，她定义了一个“魔法数”：一个数在转换为给定进制 #cf_span[b] 后，其表示中（不含前导零）从 #cf_span[0] 到 #cf_span[b - 1] 的每一个数字都出现偶数次。\n\n你需要回答 #cf_span[q] 个查询以解锁办公室。每个查询包含三个整数 #cf_span[bi]、#cf_span[li] 和 #cf_span[ri]，分别表示进制和需要统计魔法数的区间范围。\n\n输入的第一行包含 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）——查询的数量。\n\n接下来的 #cf_span[q] 行，每行包含三个用空格分隔的整数 #cf_span[bi]、#cf_span[li]、#cf_span[ri]（#cf_span[2 ≤ bi ≤ 10]，#cf_span[1 ≤ li ≤ ri ≤ 1018]）。\n\n你必须输出 #cf_span[q] 行，每行包含一个整数，对应每个查询的答案。\n\n在样例测试用例 #cf_span[1] 中，对于第一个查询，当我们将数字 #cf_span[4] 到 #cf_span[9] 转换为二进制时，得到：\n\n其中，只有 #cf_span[9] 的二进制表示具有偶数个 #cf_span[1] 和 #cf_span[0]。因此，答案是 #cf_span[1]。"},{"iden":"input","content":"输入的第一行包含 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）——查询的数量。接下来的 #cf_span[q] 行，每行包含三个用空格分隔的整数 #cf_span[bi]、#cf_span[li]、#cf_span[ri]（#cf_span[2 ≤ bi ≤ 10]，#cf_span[1 ≤ li ≤ ri ≤ 1018]）。"},{"iden":"output","content":"你必须输出 #cf_span[q] 行，每行包含一个整数，对应每个查询的答案。"},{"iden":"examples","content":"输入\n2\n2 4 9\n3 1 10\n输出\n1\n2\n\n输入\n2\n2 1 100\n5 1 100\n输出\n2\n14"},{"iden":"note","content":"在样例测试用例 #cf_span[1] 中，对于第一个查询，当我们将数字 #cf_span[4] 到 #cf_span[9] 转换为二进制时，得到： #cf_span[4 = 100_2]， #cf_span[5 = 101_2]， #cf_span[6 = 110_2]， #cf_span[7 = 111_2]， #cf_span[8 = 1000_2]， #cf_span[9 = 1001_2]。其中，只有 #cf_span[9] 的二进制表示具有偶数个 #cf_span[1] 和 #cf_span[0]。因此，答案是 #cf_span[1]。"}],"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\\} $:  \n- $ b_i \\in \\mathbb{Z} $, $ 2 \\le b_i \\le 10 $, is the base.  \n- $ l_i, r_i \\in \\mathbb{Z} $, $ 1 \\le l_i \\le r_i \\le 10^{18} $, define the range $ [l_i, r_i] $.  \n\nA number $ n \\in \\mathbb{Z}^+ $ is a *magic number* in base $ b $ if, in its base-$ b $ representation (without leading zeros), every digit $ d \\in \\{0, 1, \\dots, b-1\\} $ appears an even number of times (including zero).\n\n**Constraints**  \n1. $ 1 \\le q \\le 10^5 $  \n2. $ 2 \\le b_i \\le 10 $ for all $ i $  \n3. $ 1 \\le l_i \\le r_i \\le 10^{18} $ for all $ i $  \n\n**Objective**  \nFor each query $ i $, compute:  \n$$  \n\\left| \\left\\{ n \\in [l_i, r_i] \\,\\middle|\\, \\text{in base } b_i, \\text{ every digit } d \\in \\{0,1,\\dots,b_i-1\\} \\text{ appears an even number of times in } \\mathrm{repr}_{b_i}(n) \\right\\} \\right|  \n$$","simple_statement":null,"has_page_source":false}