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.util.HashMap;
import java.util.Scanner;

public class R932B {

    public static Scanner in;

    HashMap<Integer, Integer> cache = new HashMap<>();
    HashMap<Integer, Integer> fCache = new HashMap<>();

    int[] as = new int[1000001];
    int[][] arr = new int[10][1000001];

    void solve() {
        cacheAll();
        int q = in.nextInt();
        in.nextLine();


        int[][] arr = new int[q][];


        for (int i = 0; i < q; i++) {
            arr[i] = nai(3);
        }


        int[] ans = new int[q];


        StringBuilder stringBuilder = new StringBuilder();
        for (int i1 = 0; i1 < arr.length; i1++) {
            int[] ar = arr[i1];
            int l = ar[0];
            int r = ar[1];
            int k = ar[2];
            stringBuilder.append(get(l, r, k) + "\n");
        }
        print(stringBuilder.toString());

    }

    int get(int l, int r, int k) {
        int[] cu = arr[k];
        return cu[r] - cu[l - 1];
    }

    void cacheAll() {
        for (int i = 0; i <= 1000000; i++) {
            as[i] = g(i);
            for (int j = 1; j <= 9; j++) {
                arr[j][i] = i > 0 ? arr[j][i - 1] : 0;
            }
            arr[as[i]][i] = arr[as[i]][i] + 1;
        }
    }

    int g(int n) {
        if (n < 10) return n;
        if (cache.containsKey(n)) return cache.get(n);
        int res = g(f(n));
        cache.put(n, res);
        return res;
    }

    int f(int n) {
        if (fCache.containsKey(n)) return cache.get(n);
        int res = 1;
        for (char c : (n + "").toCharArray()) {
            int adding = c - 48;
            if (adding != 0) res *= adding;
        }
        fCache.put(n, res);
        return res;
    }

    //<editor-fold desc="Description">
    public static String[] na(int n) {
        String[] result = new String[n];
        for (int i = 0; i < n; i++) result[i] = in.nextLine();
        return result;
    }

    public static int[] nai(int n) {
        int[] result = new int[n];
        for (int i = 0; i < n; i++) result[i] = in.nextInt();
        return result;
    }

    public static Integer[] naI(int n) {
        Integer[] result = new Integer[n];
        for (int i = 0; i < n; i++) result[i] = in.nextInt();
        return result;
    }

    public static void println(String str) {
        System.out.println(str);
    }

    public static void print(String str) {
        System.out.print(str);
    }

    //
    public class Pair<A, B> {
        private A a;
        private B b;

        public Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }

        public A getA() {
            return a;
        }

        public void setA(A a) {
            this.a = a;
        }

        public B getB() {
            return b;
        }

        public void setB(B b) {
            this.b = b;
        }
    }

    public class ABHashMap<A, B> {
        private HashMap<A, B> abHashMap;
        private HashMap<B, A> baHashMap;

        public ABHashMap() {
            this.abHashMap = new HashMap<>();
            this.baHashMap = new HashMap<>();
        }

        public void put(A a, B b) {
            this.abHashMap.put(a, b);
            this.baHashMap.put(b, a);
        }

        public A getA(B b) {
            return baHashMap.get(b);
        }

        public B getB(A a) {
            return abHashMap.get(a);
        }

        public void removeByA(A a) {
            baHashMap.remove(abHashMap.get(a));
            abHashMap.remove(a);
        }

        public void removeByB(B b) {
            abHashMap.remove(baHashMap.get(b));
            baHashMap.remove(b);
        }

        public boolean containsA(A a) {
            return abHashMap.containsKey(a);
        }

        public boolean containsB(B b) {
            return baHashMap.containsKey(b);
        }
    }

    public class Triple<A, B, C> {
        private A a;
        private B b;
        private C c;

        public Triple(A a, B b, C c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        public A getA() {
            return a;
        }

        public void setA(A a) {
            this.a = a;
        }

        public B getB() {
            return b;
        }

        public void setB(B b) {
            this.b = b;
        }

        public C getC() {
            return c;
        }

        public void setC(C c) {
            this.c = c;
        }
    }

    public static void main(String[] args) {
        in = new Scanner(System.in);
        new R932B().solve();
    }
    //</editor-fold>

}