932B. Recursive Queries

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 integers x between l and r inclusive, such that g(x) = k.

Input

The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 10⁵) representing the number of queries.

Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 10⁶, 1 ≤ k ≤ 9).

Output

For each query, print a single line containing the answer for that query.

Examples Input Copy 4 22 73 9 45 64 6 47 55 7 2 62 4 Output 1 4 0 8 Input Copy 4 82 94 6 56 67 4 28 59 9 39 74 4 Output 3 1 1 5 Note

In the first example:

g(33) = 9 as g(33) = g(3 × 3) = g(9) = 9 g(47) = g(48) = g(60) = g(61) = 6 There are no such integers between 47 and 55. g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4

题意：Q次询问，求l<=x<=r内F(x)为k的x个数

#include<bits/stdc++.h> using namespace std; const int N = 1e6+5; int dp[10][N]; int F(int x){ if(x<10) return x; int sum=1; while(x){ sum*=(x>0?x:1); x/=10; } return F(sum); } void init(){ for(int i=1;i<=1000000;i++) dp[F(i)][i]++; for(int i=1;i<10;i++){ for(int j=1;j<=1000000;j++) dp[i][j]+=dp[i][j-1]; } } int main(){ init(); int Q; scanf("%d",&Q); while(Q--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",dp[k][r]-dp[k][l-1]); } return 0; }