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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskBdjkdn solver = new TaskBdjkdn();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskBdjkdn {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int arr[] = new int[(int) 1e6 + 10];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) g(i);
            }
            int arr1[] = new int[(int) 1e6 + 10];
            int arr2[] = new int[(int) 1e6 + 10];
            int arr3[] = new int[(int) 1e6 + 10];
            int arr4[] = new int[(int) 1e6 + 10];
            int arr5[] = new int[(int) 1e6 + 10];
            int arr6[] = new int[(int) 1e6 + 10];
            int arr7[] = new int[(int) 1e6 + 10];
            int arr8[] = new int[(int) 1e6 + 10];
            int arr9[] = new int[(int) 1e6 + 10];
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 1) {
                    arr1[i] = arr1[i - 1] + 1;
                } else {
                    arr1[i] = arr1[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 2) {
                    arr2[i] = arr2[i - 1] + 1;
                } else {
                    arr2[i] = arr2[i - 1];
                }
            }
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] == 3) {
                    arr3[i] = arr3[i - 1] + 1;
                } else {
                    arr3[i] = arr3[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 4) {
                    arr4[i] = arr4[i - 1] + 1;
                } else {
                    arr4[i] = arr4[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 5) {
                    arr5[i] = arr5[i - 1] + 1;
                } else {
                    arr5[i] = arr5[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 6) {
                    arr6[i] = arr6[i - 1] + 1;
                } else {
                    arr6[i] = arr6[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 7) {
                    arr7[i] = arr7[i - 1] + 1;
                } else {
                    arr7[i] = arr7[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 8) {
                    arr8[i] = arr8[i - 1] + 1;
                } else {
                    arr8[i] = arr8[i - 1];
                }
            }
            for (int i = 1; i < arr1.length; i++) {
                if (arr[i] == 9) {
                    arr9[i] = arr9[i - 1] + 1;
                } else {
                    arr9[i] = arr9[i - 1];
                }
            }
            int q = in.nextInt();
            while (q-- > 0) {
                int a = in.nextInt(), b = in.nextInt(), k = in.nextInt();
                switch (k) {
                    case 1:
                        out.println(arr1[b] - arr1[a - 1]);
                        break;
                    case 2:
                        out.println(arr2[b] - arr2[a - 1]);
                        break;
                    case 3:
                        out.println(arr3[b] - arr3[a - 1]);
                        break;
                    case 4:
                        out.println(arr4[b] - arr4[a - 1]);
                        break;
                    case 5:
                        out.println(arr5[b] - arr5[a - 1]);
                        break;
                    case 6:
                        out.println(arr6[b] - arr6[a - 1]);
                        break;
                    case 7:
                        out.println(arr7[b] - arr7[a - 1]);
                        break;
                    case 8:
                        out.println(arr8[b] - arr8[a - 1]);
                        break;
                    case 9:
                        out.println(arr9[b] - arr9[a - 1]);
                        break;
                    default:
                        break;

                }
            }
        }

        private long f(long i) {
            String str = "" + i;
            long ans = 1l;
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) - '0' == 0) {
                    continue;
                } else {
                    ans = (long) ans * (long) (str.charAt(j) - '0');
                }
            }
            return ans;
        }

        private long g(long i) {
            if (i < 10) {
                return (int) i;
            } else {
                return g(f(i));
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(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 boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}