{"raw_statement":[{"iden":"statement","content":"We call a positive integer _x_ a _k_\\-beautiful integer if and only if it is possible to split the multiset of its digits in the decimal representation into two subsets such that the difference between the sum of digits in one subset and the sum of digits in the other subset is **less than or equal to** _k_. Each digit should belong to exactly one subset after the split.\n\nThere are _n_ queries for you. Each query is described with three integers _l_, _r_ and _k_, which mean that you are asked how many integers _x_ between _l_ and _r_ (inclusive) are _k_\\-beautiful."},{"iden":"input","content":"The first line contains a single integer _n_ (1 ≤ _n_ ≤ 5·104), indicating the number of queries.\n\nEach of the next _n_ lines describes a query, containing three integers _l_, _r_ and _k_ (1 ≤ _l_ ≤ _r_ ≤ 1018, 0 ≤ _k_ ≤ 9)."},{"iden":"output","content":"For each query print a single number — the answer to the query."},{"iden":"examples","content":"Input\n\n10\n1 100 0\n1 100 1\n1 100 2\n1 100 3\n1 100 4\n1 100 5\n1 100 6\n1 100 7\n1 100 8\n1 100 9\n\nOutput\n\n9\n28\n44\n58\n70\n80\n88\n94\n98\n100\n\nInput\n\n10\n1 1000 0\n1 1000 1\n1 1000 2\n1 1000 3\n1 1000 4\n1 1000 5\n1 1000 6\n1 1000 7\n1 1000 8\n1 1000 9\n\nOutput\n\n135\n380\n573\n721\n830\n906\n955\n983\n996\n1000"},{"iden":"note","content":"If 1 ≤ _x_ ≤ 9, integer _x_ is _k_\\-beautiful if and only if _x_ ≤ _k_.\n\nIf 10 ≤ _x_ ≤ 99, integer _x_ = 10_a_ + _b_ is _k_\\-beautiful if and only if |_a_ - _b_| ≤ _k_, where _a_ and _b_ are integers between 0 and 9, inclusive.\n\n100 is _k_\\-beautiful if and only if _k_ ≥ 1."}],"translated_statement":[{"iden":"statement","content":"我们称一个正整数 #cf_span[x] 为 #cf_span[k]-美观整数，当且仅当可以将其十进制表示中的各位数字组成的多重集划分为两个子集，使得其中一个子集的数字和与另一个子集的数字和之差的绝对值 *小于或等于* #cf_span[k]。划分后，每个数字必须恰好属于其中一个子集。\n\n你有 #cf_span[n] 个查询。每个查询由三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k] 描述，表示你需要回答在区间 [#cf_span[l], #cf_span[r]]（包含端点）中有多少个整数 #cf_span[x] 是 #cf_span[k]-美观的。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·10^4]），表示查询的数量。\n\n接下来的 #cf_span[n] 行每行描述一个查询，包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 10^{18}]，#cf_span[0 ≤ k ≤ 9]）。\n\n对于每个查询，请输出一个数——该查询的答案。\n\n如果 #cf_span[1 ≤ x ≤ 9]，则整数 #cf_span[x] 是 #cf_span[k]-美观的当且仅当 #cf_span[x ≤ k]。\n\n如果 #cf_span[10 ≤ x ≤ 99]，则整数 #cf_span[x = 10a + b] 是 #cf_span[k]-美观的当且仅当 #cf_span[|a - b| ≤ k]，其中 #cf_span[a] 和 #cf_span[b] 是介于 #cf_span[0] 和 #cf_span[9] 之间的整数。\n\n#cf_span[100] 是 #cf_span[k]-美观的当且仅当 #cf_span[k ≥ 1]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·10^4]），表示查询的数量。接下来的 #cf_span[n] 行每行描述一个查询，包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 10^{18}]，#cf_span[0 ≤ k ≤ 9]）。"},{"iden":"output","content":"对于每个查询，请输出一个数——该查询的答案。"},{"iden":"examples","content":"输入\n10\n1 100 0\n1 100 1\n1 100 2\n1 100 3\n1 100 4\n1 100 5\n1 100 6\n1 100 7\n1 100 8\n1 100 9\n输出\n9\n28\n44\n58\n70\n80\n88\n94\n98\n100\n\n输入\n10\n1 1000 0\n1 1000 1\n1 1000 2\n1 1000 3\n1 1000 4\n1 1000 5\n1 1000 6\n1 1000 7\n1 1000 8\n1 1000 9\n输出\n13\n53\n80\n573\n721\n830\n906\n955\n983\n1000"},{"iden":"note","content":"如果 #cf_span[1 ≤ x ≤ 9]，则整数 #cf_span[x] 是 #cf_span[k]-美观的当且仅当 #cf_span[x ≤ k]。如果 #cf_span[10 ≤ x ≤ 99]，则整数 #cf_span[x = 10a + b] 是 #cf_span[k]-美观的当且仅当 #cf_span[|a - b| ≤ k]，其中 #cf_span[a] 和 #cf_span[b] 是介于 #cf_span[0] 和 #cf_span[9] 之间的整数。#cf_span[100] 是 #cf_span[k]-美观的当且仅当 #cf_span[k ≥ 1]。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ S(x) $ denote the multiset of decimal digits of a positive integer $ x $.\n\nA positive integer $ x $ is **$ k $-beautiful** if and only if there exists a partition of $ S(x) $ into two disjoint subsets $ A $ and $ B $, such that:\n$$\n\\left| \\sum_{d \\in A} d - \\sum_{d \\in B} d \\right| \\leq k\n$$\n\nLet $ T = \\sum_{d \\in S(x)} d $ be the total sum of digits of $ x $.  \nThen $ x $ is $ k $-beautiful if and only if there exists a subset of digits summing to $ s $, such that:\n$$\n|2s - T| \\leq k\n$$\nwhich is equivalent to:\n$$\ns \\in \\left[ \\frac{T - k}{2}, \\frac{T + k}{2} \\right]\n$$\nand $ s $ must be an integer achievable as a subset sum of $ S(x) $.\n\n---\n\n**Given:**  \n- $ n $ queries ($ 1 \\leq n \\leq 5 \\cdot 10^4 $)  \n- Each query: $ l, r, k $ with $ 1 \\leq l \\leq r \\leq 10^{18} $, $ 0 \\leq k \\leq 9 $\n\n**For each query, compute:**\n$$\n\\left| \\left\\{ x \\in \\mathbb{Z} \\mid l \\leq x \\leq r \\text{ and } x \\text{ is } k\\text{-beautiful} \\right\\} \\right|\n$$\n\n---\n\n**Special cases (from problem):**  \n- If $ 1 \\leq x \\leq 9 $: $ x $ is $ k $-beautiful $ \\iff x \\leq k $  \n- If $ 10 \\leq x \\leq 99 $, $ x = 10a + b $: $ x $ is $ k $-beautiful $ \\iff |a - b| \\leq k $  \n- $ x = 100 $ is $ k $-beautiful $ \\iff k \\geq 1 $\n\n> Note: These are illustrative edge cases; the general condition above applies to all $ x $.\n\n---\n\n**Objective:**  \nFor each query $ (l, r, k) $, compute the count of $ k $-beautiful integers in $ [l, r] $, using the subset-sum condition on digit multisets.","simple_statement":null,"has_page_source":false}