932B.md (1505B)
1 Source: https://codeforces.com/problemset/problem/932/B 2 3 B. Recursive Queries 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let us define two functions *f* and *g* on positive integer numbers. 22 23  24 25  26 27 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 integers *x* between *l* and *r* inclusive, such that *g*(*x*) = *k*. 28 29 Input 30 31 The first line of the input contains an integer *Q* (1 ≤ *Q* ≤ 2 × 105) representing the number of queries. 32 33 *Q* lines follow, each of which contains 3 integers *l*, *r* and *k* (1 ≤ *l* ≤ *r* ≤ 106, 1 ≤ *k* ≤ 9). 34 35 Output 36 37 For each query, print a single line containing the answer for that query. 38 39 Examples 40 41 Input 42 43 ``` 44 4 45 22 73 9 46 45 64 6 47 47 55 7 48 2 62 4 49 ``` 50 51 Output 52 53 ``` 54 1 55 4 56 0 57 8 58 ``` 59 60 Input 61 62 ``` 63 4 64 82 94 6 65 56 67 4 66 28 59 9 67 39 74 4 68 ``` 69 70 Output 71 72 ``` 73 3 74 1 75 1 76 5 77 ``` 78 79 Note 80 81 In the first example: 82 83 * *g*(33) = 9 as *g*(33) = *g*(3 × 3) = *g*(9) = 9 84 * *g*(47) = *g*(48) = *g*(60) = *g*(61) = 6 85 * There are no such integers between 47 and 55. 86 * *g*(4) = *g*(14) = *g*(22) = *g*(27) = *g*(39) = *g*(40) = *g*(41) = *g*(58) = 4