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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.lang.Math;

public class ACM {

    private static int gcdThing(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.intValue();
    }

    public static int binarySearch(long data[], long key) {
        int count = -1;
        int low = 0;
        int high = data.length - 1;

        while (high >= low) {
            int middle = (low + high) / 2;
            if (data[middle] == key) {

                return middle;
            }
            if (data[middle] < key) {
                low = middle + 1;
                count = middle;
            }
            if (data[middle] > key) {
                high = middle - 1;
            }
        }
        return count;
    }

    public static int f(int x) {
        int mul = 1;

        while (x != 0) {
            int m = x % 10;
            if (m != 0) {
                mul *= m;
            }
            x /= 10;
        }

        return mul;
    }

    public static int g(int x) {
        return ((x < 10) ? x : g(f(x)));
    }

    public static void main(String[] args) {
        FastScanner input = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
//////////////////////////////////////////////////////
        int[] memo;
        memo = new int[1000001];
        Arrays.fill(memo, -1);
        for (int i = memo.length - 1; i > 0; i--) {
            memo[i] = g(i);
        }

        int[][] ans = new int[10][1000001];
        for (int i = 1; i < 10; i++) {
            for (int j = 1; j < 1000001; j++) {
                if (memo[j] == i) {
                    ans[i][j] += 1 + ans[i][j - 1];
                } else {
                    ans[i][j] += ans[i][j - 1];
                }
            }
        }
        int n = input.nextInt();
        while (n-- > 0) {
            int l = input.nextInt();
            int r = input.nextInt();
            int v = input.nextInt();
            out.println(ans[v][r] - ans[v][l - 1]);
        }

//out.println("Enjoy");
        /////////////////////////////////////////////////////////
        out.flush();
        out.close();
    }// end main method 

}

class FastScanner {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastScanner(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String next() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public String nextLine() {
        int c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isLineEndChar(c));
        return res.toString();
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, nextInt());
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public boolean isLineEndChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return c == '\n' || c == '\r' || c == -1;
    }

    public interface SpaceCharFilter {

        public boolean isSpaceChar(int ch);
    }
}