Let us define two functions *f* and *g* on positive integer numbers. 

<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/120df92771639f1f51a4b216dccd3ed7c32bb859.png" style="max-width: 100.0%;max-height: 100.0%;"/> 

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*.
The first line of the input contains an integer *Q* (1 ≤ *Q* ≤ 2 × 10<sup class="upper-index">5</sup>) representing the number of queries. 

*Q* lines follow, each of which contains 3 integers *l*, *r* and *k* (1 ≤ *l* ≤ *r* ≤ 10<sup class="upper-index">6</sup>, 1 ≤ *k* ≤ 9).
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
4
22 73 9
45 64 6
47 55 7
2 62 4
1
4
0
8
4
82 94 6
56 67 4
28 59 9
39 74 4
3
1
1
5
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;

public class LineSweep {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr=new int[1000010];
        for(int i=0;i<=9;i+=1){
            arr[i]=i;
        }
        for(int i=10;i<=1000000;i+=1) {
            Integer x = i;
            recurs(x.toString(), i, arr);
        }
        int[][] ans=new int[10][1000010];
        for(int i=1;i<=1000000;i++) {
            ans[arr[i]][i] = 1;
        }
        for(int i=1;i<=9;i++){
            for(int j=1;j<=1000000;j+=1){
                ans[i][j]+=ans[i][j-1];
            }
        }
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int k=sc.nextInt();
            System.out.println(ans[k][r]-ans[k][l-1]);
        }
    }
    public static void recurs(String n,int an,int[] arr) {
        int prod = 1;
        for(int i=0;i<n.length();i++){
            if(n.charAt(i)!='0')
               prod*=Integer.parseInt(n.charAt(i)+"");
//            System.out.println(prod);
        }
//        System.out.println(an+" prod "+prod);
        arr[an]=arr[prod];
    }


}
