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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();

	}

	static class TaskC {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int data[]  =  new int[1000000+1] ; 
			ArrayList<Integer> nine = new ArrayList<Integer>() ; 
			ArrayList<Integer> eight = new ArrayList<Integer>() ; 
			ArrayList<Integer> seven = new ArrayList<Integer>() ; 
			ArrayList<Integer> six = new ArrayList<Integer>() ; 
			ArrayList<Integer> five = new ArrayList<Integer>() ; 
			ArrayList<Integer> four = new ArrayList<Integer>() ; 
			ArrayList<Integer> three = new ArrayList<Integer>() ; 
			ArrayList<Integer> two = new ArrayList<Integer>() ; 
			ArrayList<Integer> one = new ArrayList<Integer>() ; 

			for (int i = 1; i < data.length; i++)
			{
				data[i]=gett(i) ;
				switch (data[i]){
				case 1: one.add(i) ;break ;
				case 2: two.add(i) ;break ;
				case 3: three.add(i) ;break ;
				case 4:four.add(i) ;break ;
				case 5: five.add(i) ;break ;
				case 6: six.add(i) ;break ;
				case 7: seven.add(i) ;break ;
				case 8: eight.add(i) ;break ;
				case 9: nine.add(i) ;break ;
				}
			}


			int q = in.nextInt() ; 


			System.out.println("");
			for (int i = 0; i < q; i++)
			{
				int left=in.nextInt() ;
				int right = in.nextInt() ; 
				int k=in.nextInt() ;
				switch (k){
				case 1: solvE(one  , left , right) ;break ;
				case 2: solvE(two  , left , right) ;break ;
				case 3: solvE(three  , left , right) ;break ;
				case 4:solvE(four  , left , right) ;break ;
				case 5: solvE(five  , left , right) ;break ;
				case 6: solvE(six  , left , right) ;break ;
				case 7: solvE(seven  , left , right) ;break ;
				case 8: solvE(eight  , left , right) ;break ;
				case 9:solvE(nine  , left , right); break ;
				}
			}






		}

		public static void solvE(ArrayList<Integer> one, int left , int right){
			int c =0 ;
			int begin = binarySearch(one, left) ;
			int end = binarySearch(one, right) ;

			if(begin >= one.size() && one.get(begin-1)!=left)
			{
				System.out.println(0);
				return ;
			}
			if(begin >0 && one.get(begin-1)==left) begin -=1 ; 

			c = end-begin;

			System.out.println(c);
			return ;
		}
		public static int gett(int x){
			while(x>=10)
				x=get(x) ;
			return x ;
		}
		public static int get(int x){
			int sum=1 ; 
			while(x>0){
				int y =x%10 ; 
				if(y!=0)sum*=y ; 
				x=x/10 ;
			}
			return sum ;
		}
		public static int binarySearch(ArrayList<Integer> arr , int target) {
			int low = 0, high = arr.size();
			while (low != high) {
				int mid = (low + high) / 2;
				if (arr.get(mid) <= target) {
					low = mid + 1;
				}
				else {
					high = mid;
				}
			}
			return  (low) ;
		}



		public static boolean isPrime (long num){
			if (num < 2) return false;
			if (num == 2) return true;
			if (num % 2 == 0) return false;
			for (long i = 3*1l; i * i <= num; i += 2)
				if (num % i == 0) return false;
			return true;
		}
	}
	static class InputReader {
		public BufferedReader	reader;
		public StringTokenizer	tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e)
				{
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
	static class Vertix{
		int x ; 
		ArrayList<Vertix> children; 
		Vertix parent; 

		public Vertix(int x){
			this.x = x ;
			this.children= new ArrayList<Vertix>();
		}

	}

	static class Pair implements Comparable<Pair> {
		int x ; 
		int y ; 

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

		}

		@Override
		public int compareTo(Pair p) {
			if (this.x < p.x)
				return -1;
			else if (this.x > p.x)
				return 1;
			else
				return 0;

		}
		//
	}

}