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.math.*;
        		    import java.util.*;
        		    import javax.print.attribute.SetOfIntegerSyntax;
        		   
        		    
        		    		//----MAYANK SAVALIYA----//
             		
        		    
        		   public  class IO{
        		    	
        		    	private static final Exception Exception = null;
						private static InputStream stream;
        		    	private static byte[] buf = new byte[1024];
        		    	private static int curChar;
        		    	private static int numChars;
        		    	private static SpaceCharFilter filter;
        		    	private static PrintWriter pw;
        		    	
        		        public static void main(String[] args) {
        		        	InputReader(System.in);
        		    		pw = new PrintWriter(System.out); 
        		            new Thread(null ,new Runnable(){
        		               public void run(){
        		                   try{
        		                       soln2();
        		                       pw.close();
        		                   } catch(Exception e){
        		                       e.printStackTrace();
        		                   }
        		               }
        		           },"1",1<<26).start();
        		       }   		  
        		        public static int gcd(int a,int b){
        		        	if(a==0)
        		        		return b;
        		        	//System.out.println("here");
        		        	return gcd(b%a,a);
        		        	//System.out.println("here");
        		        }
        		        static class node{
        		        	int x,y;
        		        	node(int i,int j){
        		        		x = i;y = j;
        		        	}
        		        }
        		     
        		        public static int pro = 1;
        		    	public static void find(int i ){
        		    		int temp = i;
        		    		pro = 1;
        		    		while(temp>0){
        		    			int t = temp%10;
        		    			if(t!=0)
        		    				pro*=t;
        		    			temp/=10;
        		    		}
        		    		if(pro<=9)
        		    			{
        		    			//System.out.println(pro);
        		    			return;
        		    			}
        		    		else 
        		    			find(pro);
        		    	}
        		    	public static void soln2(){
        		    		//Scanner mak = new Scanner(System.in);
        		    		int n = nextInt();
        		    		long dp[] = new long[1000005];
        		    		for(int i = 1;i<=9;i++)
        		    			dp[i] = i;
        		    		for(int i = 10;i<=1000004;i++){
        		    			find(i);
        		    			dp[i] = pro;
        		    		}
        		    		int dp2[][] = new int[1000005][10];
        		    		for(int i = 1;i<=9;i++){
        		    			for(int j = 1;j<=1000000;j++){
        		    				if(dp[j]==i)
        		    					dp2[j][i] = dp2[j-1][i]+1;
        		    				else
        		    					dp2[j][i] = dp2[j-1][i];
        		    			}
        		    		}
        		    		while(n-->0){
        		    			int l =nextInt();
        		    			int r = nextInt();
        		    			int k = nextInt();
        		    			if(dp2[l][k]==0)
        		    			pw.println(dp2[r][k]);
        		    			
        		    			else
        		    				{
        		    				if(dp2[l-1][k]<dp2[l][k])
        		    				pw.println((dp2[r][k] - dp2[l][k]+1));
        		    				else 
        		    					pw.println(dp2[r][k] - dp2[l][k]);
        		    				}
        		    		}pw.close();
        		    	}
        		           		    	public static void InputReader(InputStream stream1) {
        		    		stream = stream1;
        		    	}
     
        		    	private static boolean isWhitespace(int c) {
        		    		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        		    	}
     
        		    	private static boolean isEndOfLine(int c) {
        		    		return c == '\n' || c == '\r' || c == -1;
        		    	}
     
        		    	private static 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++];
        		    	}
     
        		    	private static 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;
        		    	}
     
        		    	private static long nextLong() {
        		    		int c = read();
        		    		while (isSpaceChar(c))
        		    			c = read();
        		    		int sgn = 1;
        		    		if (c == '-') {
        		    			sgn = -1;
        		    			c = read();
        		    		}
        		    		long res = 0;
        		    		do {
        		    			if (c < '0' || c > '9')
        		    				throw new InputMismatchException();
        		    			res *= 10;
        		    			res += c - '0';
        		    			c = read();
        		    		} while (!isSpaceChar(c));
        		    		return res * sgn;
        		    	}
     
        		    	private static String nextToken() {
        		    		int c = read();
        		    		while (isSpaceChar(c))
        		    			c = read();
        		    		StringBuilder res = new StringBuilder();
        		    		do {
        		    			res.appendCodePoint(c);
        		    			c = read();
        		    		} while (!isSpaceChar(c));
        		    		return res.toString();
        		    	}
     
        		    	private static String nextLine() {
        		    		int c = read();
        		    		while (isSpaceChar(c))
        		    			c = read();
        		    		StringBuilder res = new StringBuilder();
        		    		do {
        		    			res.appendCodePoint(c);
        		    			c = read();
        		    		} while (!isEndOfLine(c));
        		    		return res.toString();
        		    	}
     
        		    	private static int[] nextIntArray(int n) {
        		    		int[] arr = new int[n];
        		    		for (int i = 0; i < n; i++) {
        		    			arr[i] = nextInt();
        		    		}
        		    		return arr;
        		    	}
     
        		    	private static int[][] next2dArray(int n, int m) {
        		    		int[][] arr = new int[n][m];
        		    		for (int i = 0; i < n; i++) {
        		    			for (int j = 0; j < m; j++) {
        		    				arr[i][j] = nextInt();
        		    			}
        		    		}
        		    		return arr;
        		    	}
        		    	private static char[][] nextCharArray(int n,int m){
        		    		char [][]c=new char[n][m];
        		    		for(int i=0;i<n;i++){
        		    			String s=nextLine();
        		    			for(int j=0;j<s.length();j++){
        		    				c[i][j]=s.charAt(j);
        		    			}
        		    		}
        		    		return c;
        		    	}
     
        		    	private static long[] nextLongArray(int n) {
        		    		long[] arr = new long[n];
        		    		for (int i = 0; i < n; i++) {
        		    			arr[i] = nextLong();
        		    		}
        		    		return arr;
        		    	}
     
        		    	private static void pArray(int[] arr) {
        		    		for (int i = 0; i < arr.length; i++) {
        		    			pw.print(arr[i] + " ");
        		    		}
        		    		pw.println();
        		    		return;
        		    	}
     
        		    	private static void pArray(long[] arr) {
        		    		for (int i = 0; i < arr.length; i++) {
        		    			pw.print(arr[i] + " ");
        		    		}
        		    		pw.println();
        		    		return;
        		    	}
     
        		    	private static void pArray(boolean[] arr) {
        		    		for (int i = 0; i < arr.length; i++) {
        		    			pw.print(arr[i] + " ");
        		    		}
        		    		pw.println();
        		    		return;
        		    	}
     
        		    	private static boolean isSpaceChar(int c) {
        		    		if (filter != null)
        		    			return filter.isSpaceChar(c);
        		    		return isWhitespace(c);
        		    	}
     
        		    	private interface SpaceCharFilter {
        		    		public boolean isSpaceChar(int ch);
        		    	}
     
     
    }