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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

import javax.swing.text.InternationalFormatter;

import java.math.*;

import org.omg.CORBA.Any;

public class template {

	static int ans = 0, mp = Integer.MAX_VALUE, k = 0;
	
	static int[][]a;

	public static void main(String[] args) throws IOException {

		Reader scn = new Reader();
		 
		int[][]a=new int[10][1000005];
		
		
		for(int i=1; i<a[0].length; i++)
			a[g(i)][i]+=1;
		
		
		for(int i=1; i<10; i++){
			 for(int j=1; j<a[0].length; j++)
				  a[i][j]+=a[i][j-1];
		}
		
		int q=scn.nextInt();
		while(q--!=0){
			
			int l=scn.nextInt(), r=scn.nextInt(), k=scn.nextInt();
			System.out.println(a[k][r]-a[k][l-1]);
		}
		 
	}
	
	
	public static int g(int n){
		  if(n<10)
			  return n;
		  
		  else  return g(f(n));
	}

	public static int f(int n){
		int p=1;
		while(n!=0){
			
			int x=n%10;
			
			if(x!=0)
				 p=p*x;
			n/=10;
		}
		return p;
	}

	// _________________________TEMPLATE_____________________________________________________________

	static class pair implements Comparable<pair> {
		int v;
		int cnt;
//		int cnt;

		pair(int b, int a) {
			v = b;
			cnt = a;
//			cnt = x;
		}

		@Override
		public int compareTo(pair o) {

			 if(this.cnt != o.cnt)
				  return this.cnt - o.cnt;
			 else return this.v - o.v;
		}
	}

	// -----------PrintWriter for faster output---------------------------------
	public static PrintWriter out;

	public static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[100000 + 1]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) throws IOException {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLong();
			}
			return arr;
		}

		public int[][] nextInt2DArray(int m, int n) throws IOException {
			int[][] arr = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++)
					arr[i][j] = nextInt();
			}
			return arr;
		}

	}

	// private static void rem(HashMap<Integer, Integer> hm) {
	//
	// Iterator<Map.Entry<Integer, Integer>> itr = hm.entrySet().iterator();
	// ArrayList<Integer> p=new ArrayList<>();
	//
	//
	// while(itr.hasNext()){
	// Map.Entry<Integer, Integer> entry = itr.next();
	// p.add(entry.getKey());
	//
	// }
	//
	//
	// for(int i:p){
	//
	// if(hm.get(i)>1)
	// hm.put(i, hm.get(i)-1);
	// else
	// hm.remove(i);
	// }
	// }

}