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

<image>

<image>

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 × 105) representing the number of queries. 

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

Output

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

Examples

Input

4
22 73 9
45 64 6
47 55 7
2 62 4


Output

1
4
0
8


Input

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

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

public class Template {

    class Edge{
        int to;
        int num;
        Edge(int to, int num){
            this.to = to;
            this.num = num;
        }
    }

    class Vertex{
        int x, y;
        Vertex(int x, int y){
            this.x = x;
            this.y = y;
        }

    }
    String fileName = "";
    int MODULO = 1000*1000*1000+7;
    ArrayList<Integer>[] graph;
    void solve() throws IOException {
        int k = readInt();
        int[][] prefSum = new int[10][1000*1000+100];

        for(int i=1; i<=1000*1000; ++i){
            int cur = i;


            while(cur>=10){
                int sum = 1;
                int cur1 = cur;
                while(cur1>0){
                    sum *= Math.max(1, cur1 % 10);
                    cur1 /= 10;
                }

                cur = sum;

            }
            prefSum[cur][i] = 1;

        }
        for(int i=1; i<=9; ++i){
            for(int j=1; j<=1000*1000; ++j) {
                prefSum[i][j] += prefSum[i][j - 1];
            }
        }
        for(int i=0; i<k; ++i){
            int l = readInt();
            int r = readInt();
            int d = readInt();
            out.println(prefSum[d][r] - prefSum[d][l-1]);
        }
    }


    boolean isLower(char c){
        return c >= 'a' && c <= 'z';
    }

    ////////////////////////////////////////////////////////////
    class Pair{
        int num;
        int val;
        Pair(int num, int val ){
            this.num = num;
            this.val = val;
        }
    }
    /*
    class SegmentTree {
        int start = 0;
        int end = 0;
        long delta;
        int n;
        long result;
        long[] t;
        boolean[] lazy;
        int[] length;
        Pair[] segments;
        SegmentTree(int n, int[] a){
            this.n = n;
            t = new long[4*n];
            lazy = new boolean[4*n];
            length = new int[4*n];
            segments = new Pair[4*n];
            build(a, 1, 1, n);
        }

        void build(int[] a, int v, int tl, int tr){
            if(tl>tr) return;
            if(tl == tr){
                t[v] = a[tl];
                length[v] = 1;
                return;
            }
            int mid = (tl+tr)/2;
            build(a, 2*v, tl, mid);
            build(a, 2*v+1, mid+1, tr);
            length[v] = tr - tl +1;
            t[v] = t[2*v] + t[2*v+1];
        }
        void pushVertex(int v, int vLeft, int vRight){
            lazy[vLeft] += lazy[v];
            lazy[vRight] += lazy[v];
            lazy[v] = 0;
        }

        void updateVertex(int v, int vLeft, int vRight){
            t[v] = getSum(vLeft) + getSum(vRight);
        }

        long getSum(int v){
            return t[v] + lazy[v] * length[v];
        }

        void incSegment(int start, int end, long delta){
            this.start = start;
            this.end = end;
            this.delta = delta;
            incSegment(1, 1, n);
        }

        void incSegment(int v, int l, int r){
            if(start <= l && r <= end){
                lazy[v] += delta;
            }else{
                int mid = (r+l)/2;
                int vLeft = (v << 1);
                int vRight = vLeft + 1;
                pushVertex(v, vLeft, vRight);

                if(start <= mid) incSegment(vLeft, l, mid);
                if(end >= mid +1) incSegment(vRight, mid+1, r);

                updateVertex(v, vLeft, vRight);
            }
        }

        long getSegment(int start, int end){
            this.start = start;
            this.end = end;
            this.result = 0;
            getSegment(1, 1, n);
            return result;
        }
        void getSegment(int v, int l, int r){
            if(start <= l && r <= end){
                result += getSum(v);
            }else{
                int mid = (r+l)/2;
                int vLeft = (v << 1);
                int vRight = vLeft + 1;
                pushVertex(v, vLeft, vRight);

                if(start <= mid) getSegment(vLeft, l, mid);
                if(end >= mid +1) getSegment(vRight, mid+1, r);

                updateVertex(v, vLeft, vRight);
            }
        }
    }
*/
    class Fenwik {
        long[] t;
        int length;

        Fenwik(int[] a) {
            length = a.length + 100;
            t = new long[length];

            for (int i = 0; i < a.length; ++i) {
                inc(i, a[i]);
            }
        }

        void inc(int ind, int delta) {
            for (; ind < length; ind = ind | (ind + 1)) {
                t[ind] += delta;
            }
        }

        long getSum(int r) {
            long sum = 0;
            for (; r >= 0; r = (r & (r + 1)) - 1) {
                sum += t[r];
            }
            return sum;
        }
    }
    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }

    long binPow(long a, long b, long m) {
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 1) {
            return ((a % m) * (binPow(a, b - 1, m) % m)) % m;
        } else {
            long c = binPow(a, b / 2, m);
            return (c * c) % m;
        }

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Template().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    };

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";
    Random rnd = new Random();

    Template() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }
    byte readByte() throws NumberFormatException, IOException {
        return Byte.parseByte(readString());
    }
    int[] readIntArray (int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }
    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}