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

import static java.lang.Integer.compare;
import static java.lang.Math.*;
import static java.lang.System.in;
import static java.lang.System.out;
import static java.util.Arrays.deepToString;

/*
 *
 *15/2/18
 *8:14 PM
 *remedy441
 *
 */
public class CF932 {
    public static int mod = (int) (1e9 + 7);
    public static InputReader in;
    public static PrintWriter out;


    public static void solve() throws FileNotFoundException {

    	in = new InputReader(System.in);
    	out = new PrintWriter(System.out);

    	int dp[] = new int[1000001];
    	int dp2[][] = new int[1000001][10];

    	for(int i=1;i<=1000000;i++){
    	    dp[i]=i;
    	    while(dp[i]>=10){
    	        int x = dp[i];
    	        int c = 1;
    	        while(x>0){
    	            int a = x%10;
    	            x = x/10;
    	            if(a!=0)
    	                c = c*a;
                }
                dp[i] = c;
            }
        }
        for(int i =1 ;i<=1000000;i++){
    	    for(int j=1;j<=9;j++){
                dp2[i][j] = dp2[i-1][j];
    	        if(dp[i]==j)
    	            dp2[i][j] = dp2[i-1][j]+1;

            }
        }
        /*long sum = 0;
        for(int i=1;i<=9;i++){
    	    sum+=dp2[1000000][i];
        }
        out.println(sum);*/
        int q = in.ni();
    	while(q-->0){
    	    int l = in.ni();
    	    int r = in.ni();
    	    int k = in.ni();

    	    out.println(dp2[r][k]-dp2[l-1][k]);
        }

    	out.close();
    }
    public static void main(String[] args) {
    	new Thread(null, new Runnable() {
    		public void run() {
    			try {
    				solve();
    			} catch (Exception e) {
    				e.printStackTrace();
    			}
    		}
    	}, "1", 1 << 26).start();
    }

    static class Pair implements Comparable<Pair> {

    	int x, y, i;

    	Pair(int x, int y, int i) {
    		this.x = x;
    		this.y = y;
    		this.i = i;
    	}

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

    	public int compareTo(Pair o) {
    		if (this.x != o.x)
    			return compare(this.x, o.x);
    		else
    			return compare(this.y, o.y);
    		//return 0;
    	}

    	public boolean equals(Object o) {
    		if (o instanceof Pair) {
    			Pair p = (Pair) o;
    			return p.x == x && p.y == y && p.i == i;
    		}
    		return false;
    	}

    	public int hashCode() {
    		return new Integer(x).hashCode() * 31 + new Integer(y).hashCode() + new Integer(i).hashCode() * 37;
    	}

    }

    public static long add(long a, long b) {
    	long x = (a + b);
    	while (x >= mod)
    		x -= mod;
    	return x;
    }

    public static long sub(long a, long b) {
    	long x = (a - b);
    	while (x < 0)
    		x += mod;
    	return x;
    }

    public static long mul(long a, long b) {
    	long x = (a * b);
    	while (x >= mod)
    		x -= mod;
    	return x;
    }

    public static boolean isPal(String s) {
    	for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {
    		if (s.charAt(i) != s.charAt(j))
    			return false;
    	}
    	return true;
    }

    public static String rev(String s) {
    	StringBuilder sb = new StringBuilder(s);
    	sb.reverse();
    	return sb.toString();
    }

    public static long gcd(long x, long y) {
    	if (x % y == 0)
    		return y;
    	else
    		return gcd(y, x % y);
    }

    public static int gcd(int x, int y) {
    	if (x % y == 0)
    		return y;
    	else
    		return gcd(y, x % y);
    }

    static int modInverse(int a, int m) {
    	int m0 = m, t, q;
    	int x0 = 0, x1 = 1;
    	if (m == 1)
    		return 0;
    	while (a > 1) {
    		// q is quotient
    		q = a / m;
    		t = m;
    		// m is remainder now, process same as
    		// Euclid's algo
    		m = a % m;
    		a = t;
    		t = x0;
    		x0 = x1 - q * x0;
    		x1 = t;
    	}
    	// Make x1 positive
    	if (x1 < 0)
    		x1 += m0;
    	return x1;
    }

    public static long gcdExtended(long a, long b, long[] x) {

    	if (a == 0) {
    		x[0] = 0;
    		x[1] = 1;
    		return b;
    	}
    	long[] y = new long[2];
    	long gcd = gcdExtended(b % a, a, y);

    	x[0] = y[1] - (b / a) * y[0];
    	x[1] = y[0];

    	return gcd;
    }

    public static long mulmod(long a, long b, long m) {
    	if (m <= 1000000009)
    		return a * b % m;

    	long res = 0;
    	while (a > 0) {
    		if ((a & 1) != 0) {
    			res += b;
    			if (res >= m)
    				res -= m;
    		}
    		a >>= 1;
    		b <<= 1;
    		if (b >= m)
    			b -= m;
    	}
    	return res;
    }

    public static int abs(int a, int b) {
    	return (int) Math.abs(a - b);
    }

    public static long abs(long a, long b) {
    	return (long) Math.abs(a - b);
    }

    public static int max(int a, int b) {
    	if (a > b)
    		return a;
    	else
    		return b;
    }

    public static int min(int a, int b) {
    	if (a > b)
    		return b;
    	else
    		return a;
    }

    public static long max(long a, long b) {
    	if (a > b)
    		return a;
    	else
    		return b;
    }

    public static long min(long a, long b) {
    	if (a > b)
    		return b;
    	else
    		return a;
    }

    public static long pow(long n, long p, long m) {
    	long result = 1;
    	if (p == 0)
    		return 1;
    	if (p == 1)
    		return n;
    	while (p != 0) {
    		if (p % 2 == 1)
    			result *= n;
    		if (result >= m)
    			result %= m;
    		p >>= 1;
    		n *= n;
    		if (n >= m)
    			n %= m;
    	}
    	return result;
    }

    public static long pow(long n, long p) {
    	long result = 1;
    	if (p == 0)
    		return 1;
    	if (p == 1)
    		return n;
    	while (p != 0) {
    		if (p % 2 == 1)
    			result *= n;
    		p >>= 1;
    		n *= n;
    	}
    	return result;
    }

    public static void debug(Object... o) {
    	System.out.println(deepToString(o));
    }

    static class InputReader {
    	private final InputStream stream;
    	private final byte[] buf = new byte[8192];
    	private int curChar, snumChars;
    	private SpaceCharFilter filter;

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

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

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

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

    	public int[] nIArr(int n) {
    		int a[] = new int[n];
    		for (int i = 0; i < n; i++) {
    			a[i] = ni();
    		}
    		return a;
    	}

    	public long[] nLArr(int n) {
    		long a[] = new long[n];
    		for (int i = 0; i < n; i++) {
    			a[i] = nl();
    		}
    		return a;
    	}

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

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

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

    	private boolean isEndOfLine(int c) {
    		return c == '\n' || c == '\r' || c == -1;
    	}

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

    }

}