{"raw_statement":[{"iden":"statement","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_."},{"iden":"input","content":"The 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)."},{"iden":"output","content":"For each query, print a single line containing the answer for that query."},{"iden":"examples","content":"Input\n\n4\n22 73 9\n45 64 6\n47 55 7\n2 62 4\n\nOutput\n\n1\n4\n0\n8\n\nInput\n\n4\n82 94 6\n56 67 4\n28 59 9\n39 74 4\n\nOutput\n\n3\n1\n1\n5"},{"iden":"note","content":"In 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"}],"translated_statement":[{"iden":"statement","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"},{"iden":"input","content":"输入的第一行包含一个整数 #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]）。"},{"iden":"output","content":"对于每个查询，输出一行，包含该查询的答案。"},{"iden":"examples","content":"输入\n4\n22 73 9\n45 64 6\n47 55 7\n26 24 2\n输出\n1\n4\n0\n8\n\n输入\n4\n82 94 6\n56 67 4\n28 59 9\n39 74 4\n输出\n3\n1\n1\n5"},{"iden":"note","content":"在第一个例子中：#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]。"}],"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":null,"has_page_source":false}