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.util.*;


public class Main {
    BufferedReader br;
    StringTokenizer in;
    PrintWriter pw;
    Random r;
    int INF = (int) 1e9;
    long LNF = (long) 1e18;
    long mod = (long) (1e9 + 7);
    int pp = 27;
    // you shall not hack!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    //        /*\
    //       ///          /^\
    //      ///    ~~~~  (___)
    //     ///   ~~~~~~~~  \\__
    //   _/_/_  ~/ .& . \~  \\ \
    //  [____] ~|  (__)  |~/ \\/
    //  /_/\  \~|~~~~~~~~~~  /\\
    //      \   ~~~~~~~~~~ _/ \\
    //       \ _    ~~   _/\   \\
    //      /  |        /   \   \\
    //     |  /        |     \   \\
    //    /  /   ___   |      \
    //   /___|  | __|  |_______\
    //      _|  |   |  |_
    //     |____|   |____|
    //       P.S this is omnipotent Gandalf

    int solve2() throws IOException {
        BufferedReader br2 = new BufferedReader(new FileReader("input.txt"));
        int n = Integer.parseInt(br2.readLine());
        int a[] = new int[n];
        StringTokenizer in2 = new StringTokenizer(br2.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(in2.nextToken());
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int z = 0;
            for (int j = 0; j < i; j++) {
                if (a[j] + j > i) z++;
            }
            ans += z * a[i];
        }
        return ans;
    }

    long p[] = new long[(int) (2 * 1e5 + 1)];
    hash prefs[];
    hash preft[];

    hash getHashS(int l, int r) {
        hash ans = prefs[r + 1];
        ans.h += mod;
        ans.h -= prefs[l].h;
        ans.h %= mod;
        ans.firstp = l;
        ans.sz = r - l + 1;
        return ans;
    }

    hash getHashT(int l, int r) {
        hash ans = preft[r + 1];
        ans.h += mod;
        ans.h -= preft[l].h;
        ans.h %= mod;
        ans.firstp = l;
        ans.sz = r - l + 1;
        return ans;
    }

    class hash implements Comparable<hash> {
        long h;
        int sz;
        int firstp;

        public hash(String s) {
            firstp = 0;
            sz = s.length();
            for (int i = 0; i < sz; i++) {
                h += (s.charAt(i) * p[i]) % mod;
                h %= mod;
            }
        }

        public hash(hash z, char c) {
            firstp = z.firstp;
            sz = z.sz + 1;
            h = (z.h + (c * p[sz - 1]) % mod) % mod;
        }

        @Override
        public int compareTo(hash o) {
            if (sz != o.sz) return sz - o.sz;
            if (firstp > o.firstp) {
                return Long.compare(h, (o.h * p[firstp - o.firstp]) % mod);
            }
            return Long.compare((h * p[o.firstp - firstp]) % mod, o.h);
        }
    }

    void solve() throws IOException {
        int q = nextInt();
        int g[] = new int[(int) (1e6 + 1)];
        for (int i = 0; i < g.length; i++) {
            if (i < 10) g[i] = i;
            else g[i] = g[f(i)];
        }
        int pref[][] = new int[10][(int) (1e6 + 1)];
        for (int i = 0; i < 1e6 + 1; i++) {
            if (i == 0) {

            } else {
                for (int j = 0; j < 10; j++) {
                    pref[j][i] = pref[j][i - 1];
                }
            }
            pref[g[i]][i]++;
        }
        for (int i = 0; i < q; i++) {
            int l = nextInt();
            int r = nextInt();
            int k = nextInt();
            pw.println(pref[k][r] - pref[k][l - 1]);
        }
    }

    //***************************************
    class road {
        int to;

        int w;

        public road(int tto, int ww) {
            to = tto;
            w = ww;
        }
    }

    class pair {
        int a;

        int b;

        public pair(int aa, int bb) {
            a = aa;
            b = bb;
        }

    }

    Comparator<pair> bya = new Comparator<pair>() {
        @Override
        public int compare(pair o1, pair o2) {
            if (o1.a != o2.a) return Integer.compare(o1.a, o2.a);
            return Integer.compare(o1.b, o2.b);
        }
    };

    Comparator<pair> byb = new Comparator<pair>() {
        @Override
        public int compare(pair o1, pair o2) {
            if (o1.b != o2.b) return Integer.compare(o1.b, o2.b);
            return Integer.compare(o1.a, o2.a);
        }
    };
    Comparator<road> byw = new Comparator<road>() {
        @Override
        public int compare(road o1, road o2) {
            if (o1.w != o2.w) return Integer.compare(o1.w, o2.w);
            return Integer.compare(o1.to, o2.to);
        }
    };
    Comparator<road> byto = new Comparator<road>() {
        @Override
        public int compare(road o1, road o2) {
            return Integer.compare(o1.to, o2.to);
        }
    };

    class node {
        int sz;
        int val;
        //        long sum;
        node L;
        node R;
        int prior;

        public node(int val) {
            this.val = val;
            prior = r.nextInt();
            L = null;
            R = null;
            sz = 1;
//            sum = (long)val * val;
        }

        void add(int z) {
            val = val + z;
//            sum = (long)val * val;
        }
    }

    void relax(node c) {
        if (c == null) return;
        c.sz = sfsz(c.L) + sfsz(c.R) + 1;
//        c.sum = sfsum(c.L) + sfsum(c.R) + c.val * c.val;
    }

    int sfsz(node c) {
        if (c == null) return 0;
        return c.sz;
    }

    node merge(node a, node b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.prior > b.prior) {
            a.R = merge(a.R, b);
            relax(a);
            return a;
        } else {
            b.L = merge(a, b.L);
            relax(b);
            return b;
        }
    }

    pairn split(node c, int s) {
        if (c == null) return new pairn(null, null);
        if (sfsz(c.L) >= s) {
            pairn p = split(c.L, s);
            c.L = p.b;
            relax(c);
//            relax(p.a);
            return new pairn(p.a, c);
        } else {
            pairn p = split(c.R, s - sfsz(c.L) - 1);
            c.R = p.a;
            relax(c);
//            relax(p.b);
            return new pairn(c, p.b);
        }
    }

    class pairn {
        node a;
        node b;

        public pairn(node a, node b) {
            this.a = a;
            this.b = b;
        }

    }

    String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }
        return in.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }


    int f(int z) {
        int ans = 1;
        int zz = z;
        while (zz > 0) {
            if (zz % 10 != 0) {
                ans *= zz % 10;
            }
            zz /= 10;
        }
        return ans;
    }


    //    boolean check()
    public void run() throws IOException {
        r = new Random(5);
//        PrintWriter pp = new PrintWriter(new OutputStreamWriter(System.out));
//        for (int i = 0; i < 100; i++) {
//            gener();
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new OutputStreamWriter(System.out));
//        br = new BufferedReader(new FileReader("input.txt"));
//        pw = new PrintWriter(new FileWriter("output.txt"));
//        br = new BufferedReader(new FileReader("holidays.in"));
//        pw = new PrintWriter(new FileWriter("holidays.out"));
        solve();
//            int z = solve2();
//            if (a != z) {
//                pp.print("found");
//                pp.println();
//                pp.println(a);
//                pp.println(z);
//                pp.close();
//                return;
//            }
//            pp.print(i);
//        }
        pw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}