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 java.text.*;
import java.math.*;
import java.util.regex.*;
 
public class Main
{
    
    static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;

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

		public int read() {
			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 = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nl() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

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

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

		public 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();
		}

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

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

	}
	static int prob(int x)
	{
	    int r = 1;
	    if(x < 10)
	    return x;
	    else
	    {
	        int t = x;
	        while(t != 0)
	        {
	           if(t % 10 != 0)
	           r *= (t % 10);
	           t /= 10;
	            
	        }
	        return prob(r);
	    }
	}
	



    public static void main(String[] args)
    {
        
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
         int q = sc.ni();
         int []arr = new int[1000001];
         for(int i=1;i<1000001;i++)
         {
             arr[i] = prob(i);
         }
         int [][]ans = new int[10][1000001];
         for(int i=1;i<1000001;i++)
         {
             ans[arr[i]][i]++;
             for(int k=0;k<10;k++)
             {
                 ans[k][i] += ans[k][i-1];
             }
         }
        while(q-- > 0)
        {
            int c = 0;
            int x = sc.ni();
            int y = sc.ni();
            int k = sc.ni();
            
            w.println(ans[k][y]-ans[k][x-1]);
        }
        
      
          
        /*
        int x = sc.ni();
        int y = sc.ni();
        String [][]arr = new String[x+2][y+2];
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                arr[i][j] = sc.rs();
            }
        }
        int c = 0;
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                if(arr[i][j].equals("S"))
                {
                    if(arr[i-1][j].equals("W") ||arr[i+1][j].equals("W")||arr[i][j-1].equals("W")||arr[i][j+1].equals("W"))
                    c++;
                }
            }
        }
        if(c != 0)
        w.println("No");
        else
        {
            for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                if(arr[i][j].equals("S"))
                {
                    if(arr[i-1][j].equals("."))
                    arr[i-1][j].replace(".","D");
                    
                    if(arr[i+1][j].equals("."))
                    arr[i+1][j].replace(".","D");
                    
                    if(arr[i][j+1].equals("."))
                    arr[i][j+1].replace(".","D");
                    
                    if(arr[i][j-1].equals("."))
                    arr[i][j-1].replace(".","D");
                    
                    
                }
            }
        }
        w.println("Yes");
        
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                w.print(arr[i][j]);
                
            }
            w.println();
        }
        }
        
        */
        
        
        /*
        118B
        int x = sc.ni();
        int res = x*2;
        String [][]arr = new String[res+ 1][res+1];
        
        for(int i=0;i<=x*2;i++)
        {
            for(int j=x-i;j<=x+i;j++)
            {
                if(j <= x)
                    arr[i][j] = ips(i+j-x);
                    else
                     arr[i][j] = ips(2*x -i - j);
                
            }
            
        }
        for(int i=0;i<=x*2;i++)
        {
            for(int j=0;j<=x*2;j++)
            {
                w.print(arr[i][j] + " ");
                
            }
            w.println();
        }
    */
       
        
        
        
          
       
       
      
       
        
        
        
           
        
       
           
           
        
        
        
    
        w.close();
        

        
    } 
    /*
    static boolean is(int p,int x,int y)
    {
        int flag = 0;
        
            for(int j=2;j<=p;j++)
            {
                if(x % j == 0)
                {
                    flag = 1;
                    break;
                }
                else 
                continue;
                
            }
            
        if(flag == 1)
        return false;
        else
        return true;
        
    }
    */
    static int binarysearch(int []arr,int p,int n)
    {
        
        int st = 0;
        int end = n-1;
        int mid = (st + end)/2;
        int temp = 0;
        while(st <= end)
        { 
            mid = (st + end)/2;
        
            if(p >= arr[mid])
            {
                st = mid+1;
                
            }
            else if(p < arr[mid])
            {
                end = mid-1;
                
            }
            temp = st;
            
            
        }
        
        return temp;
    }
    
   
    static class Student
    {
        int start;
        int end;
        int index;
        Student(int start,int end,int index)
        {
            this.start = start;
            this.end = end;
            this.index = index;
            
        }
        
    }
    static int lis(int arr[],int n)
    {
          int lis[] = new int[n];
          int i,j,max = 0;
 
          /* Initialize LIS values for all indexes */
           for ( i = 0; i < n; i++ )
              lis[i] = 1;
 
           /* Compute optimized LIS values in bottom up manner */
           for ( i = 1; i < n; i++ )
              for ( j = 0; j < i; j++ ) 
                         if ( arr[i] > arr[j] && lis[i] <= lis[j])
                    lis[i]++;
 
           /* Pick maximum of all LIS values */
           for ( i = 0; i < n; i++ )
              if ( max < lis[i] )
                 max = lis[i];
 
            return max;
    }
    
    
    public static int ip(String s){
		return Integer.parseInt(s);
	}
	 public static String ips(int s){
		return Integer.toString(s);
	}
	
    
					 
}