{"problem":{"name":"B. Recursive Queries","description":{"content":"Let us define two functions _f_ and _g_ on positive integer numbers. You need to process _Q_ queries. In each query, you will be given three integers _l_, _r_ and _k_. You need to print the number of","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF932B"},"statements":[{"statement_type":"Markdown","content":"Let us define two functions _f_ and _g_ on positive integer numbers.\n\nYou need to process _Q_ queries. In each query, you will be given three integers _l_, _r_ and _k_. You need to print the number of integers _x_ between _l_ and _r_ inclusive, such that _g_(_x_) = _k_.\n\n## Input\n\nThe first line of the input contains an integer _Q_ (1 ≤ _Q_ ≤ 2 × 105) representing the number of queries.\n\n_Q_ lines follow, each of which contains 3 integers _l_, _r_ and _k_ (1 ≤ _l_ ≤ _r_ ≤ 106, 1 ≤ _k_ ≤ 9).\n\n## Output\n\nFor each query, print a single line containing the answer for that query.\n\n[samples]\n\n## Note\n\nIn the first example:\n\n*   _g_(33) = 9 as _g_(33) = _g_(3 × 3) = _g_(9) = 9\n*   _g_(47) = _g_(48) = _g_(60) = _g_(61) = 6\n*   There are no such integers between 47 and 55.\n*   _g_(4) = _g_(14) = _g_(22) = _g_(27) = _g_(39) = _g_(40) = _g_(41) = _g_(58) = 4","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"我们定义两个函数 #cf_span[f] 和 #cf_span[g] 作用于正整数上。\n\n你需要处理 #cf_span[Q] 个查询。在每个查询中，你会得到三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]。你需要输出在区间 #cf_span[l] 到 #cf_span[r]（包含端点）中，满足 #cf_span[g(x) = k] 的整数 #cf_span[x] 的个数。\n\n输入的第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 2 × 105]），表示查询的个数。\n\n接下来 #cf_span[Q] 行，每行包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9]）。\n\n对于每个查询，输出一行，包含该查询的答案。\n\n在第一个例子中：\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[Q]（#cf_span[1 ≤ Q ≤ 2 × 105]），表示查询的个数。#cf_span[Q] 行接下来，每行包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 106, 1 ≤ k ≤ 9]）。\n\n## Output\n\n对于每个查询，输出一行，包含该查询的答案。\n\n[samples]\n\n## Note\n\n在第一个例子中：#cf_span[g(33) = 9]，因为 #cf_span[g(33) = g(3 × 3) = g(9) = 9]；#cf_span[g(47) = g(48) = g(60) = g(61) = 6]；在 #cf_span[47] 和 #cf_span[55] 之间不存在满足条件的整数；#cf_span[g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ f, g : \\mathbb{Z}^+ \\to \\mathbb{Z}^+ $ be two functions defined on positive integers.  \n\n**Constraints**  \n1. $ Q \\in \\mathbb{Z} $, $ 1 \\leq Q \\leq 2 \\times 10^5 $  \n2. For each query:  \n   - $ l, r, k \\in \\mathbb{Z} $  \n   - $ 1 \\leq l \\leq r \\leq 10^6 $  \n   - $ 1 \\leq k \\leq 9 $  \n\n**Objective**  \nFor each query $ (l, r, k) $, compute:  \n$$\n\\left| \\left\\{ x \\in \\mathbb{Z} \\mid l \\leq x \\leq r \\text{ and } g(x) = k \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF932B","tags":["binary search","data structures","dfs and similar"],"sample_group":[["4\n22 73 9\n45 64 6\n47 55 7\n2 62 4","1\n4\n0\n8"],["4\n82 94 6\n56 67 4\n28 59 9\n39 74 4","3\n1\n1\n5"]],"created_at":"2026-03-03 11:00:39"}}