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.BigInteger;
import java.util.*;

public class MainA
{
	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;
	private static long mod = 1000000000 + 7;
	static double ans=0;
	public static double dfs(int visited[],ArrayList<Integer> adj[],int v)
	{
		visited[v]=1;int count=0;double tem=0;
		for(int i=0;i<adj[v].size();i++)
		{
			if(visited[adj[v].get(i)]==0)
			{
				double d=dfs(visited,adj,adj[v].get(i));
				count++;
				tem+=d+1;
			}
		}
		
		double var=0;
		if(count!=0)var=tem/count;
		//pw.println(v+" "+ans+" "+var+" "+count);
		ans=ans+var;
		return var;
		
	}
	
	public static int find(Pair subsets[], int i)
	{
	    // find root and make root as parent of i (path compression)
	    if (subsets[i].x != i)
	        subsets[i].x = find(subsets, subsets[i].x);
	 
	    return subsets[i].x;
	}
	 
	// A function that does union of two sets of x and y
	// (uses union by rank)
	public static void Union(Pair subsets[], int x, int y)
	{
	    int xroot = find(subsets, x);
	    int yroot = find(subsets, y);
	 
	    // Attach smaller rank tree under root of high rank tree
	    // (Union by Rank)
	    if (subsets[xroot].y < subsets[yroot].y)
	        subsets[xroot].x = yroot;
	    else if (subsets[xroot].y> subsets[yroot].y)
	        subsets[yroot].x = xroot;
	 
	    // If ranks are same, then make one as root and increment
	    // its rank by one
	    else
	    {
	        subsets[yroot].x = xroot;
	        subsets[xroot].y++;
	    }
	}
	 
	// The main function to check whether a given graph contains cycle or not
	public static int isCycle(int v1, int e1,String s1,String s2)
	{
	    int V = v1;
	    int E = e1;
	 
	    // Allocate memory for creating V sets
	    Pair subsets[]=new Pair[V];
	 
	    for (int v = 0; v < V; ++v)
	    {
	    	subsets[v]=new Pair(v,0);
	        
	    }
	 
	    // Iterate through all edges of graph, find sets of both
	    // vertices of every edge, if sets are same, then there is
	    // cycle in graph.
	    int count=0;
	    ArrayList<String> arr=new ArrayList();
	    for(int e = 0; e < E; ++e)
	    {
	        int x = find(subsets, s1.charAt(e)-'a');
	        int y = find(subsets, s2.charAt(e)-'a');
	 
	        if (x != y)
	        {  
	        	count++;
	        	arr.add(s1.charAt(e)+" "+s2.charAt(e));
	        	Union(subsets, x, y);
	        }
	    }
	    pw.println(count);
	    for(int i=0;i<count;i++)
	    {
	    	pw.println(arr.get(i));
	    }
	    return 0;
	}
	 
	private static void soln()
	{
		int q=nextInt();
		int dp[][]=new int[(int)1e6+1][10];
		int f[]=new int[(int)1e6+1];int g[]=new int[(int)1e6+1];
		for(int i=1;i<=(int)1e6;i++)
		{
			f[i]=fun(i);
		}
		
		for(int i=1;i<=(int)1e6;i++)
		{
			g[i]=gun(i,f);
			for(int j=1;j<10;j++)
			{
				if(g[i]==j)dp[i][j]=dp[i-1][j]+1;
				else dp[i][j]=dp[i-1][j];
			}
		}
		
		while(q-->0)
		{
			int l=nextInt();
			int r=nextInt();
			int k=nextInt();
			pw.println(dp[r][k]-dp[l-1][k]);
		}
		
	}
	public static int gun(int x,int f[])
	{
		if(x<10)return x;
		else
		{
			return gun(f[x],f);
		}
	}
	public static int fun(int x)
	{
		int ans=1;
		while(x>0)
		{
			int r=x%10;
			if(r!=0)
			ans*=r;
			
			x/=10;
			
		}
		return ans;
	}
	static class Pair implements Comparable<Pair>
    {

        int x,y,i;
        
        Pair (int x, int y)
        {
		this.x = x;
                this.y = y;
                
	}
	
	public int compareTo(Pair o) {
                return -Integer.compare(this.y,o.y);
	}

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

        @Override
        public String toString()
        {
            return x + " "+ y;
        }
        
        public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 

	
	public static int biSe(int x,int n)
	{
		int y=n*n-x;
		int l=1,r=n;
		while(l<=r)
		{
			int mid=(l+r)/2;
			//pw.println(mid+" "+f(mid,n)+" "+y);
			if(f(mid,n)==y)
			{
				return mid;
			}
			else if(f(mid,n)<y)
			{
				r=mid-1;
			}
			else l=mid+1;
		}
		return -1;
	}
	
	public static int f(int x,int n)
	{
		return (n/x)*(n/x);
	}
	public static class Segment 
	{
		private int[] tree;
		private boolean[] lazy;
		private int size;
		private int n;
		private class node
		{
			private int a;
			private int b;
			private int c;
			public node(int x,int y,int z)
			{
				a=x;
				b=y;
				c=z;
			}
		}
		public Segment(int n)
		{
			//this.base=arr;
			int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
	        size = 2 * (int) Math.pow(2, x) - 1;
			tree=new int[size];
			lazy=new boolean[size];
			this.n=n;
			build(0,0,n-1);
		}
		public void build(int id,int l,int r)
		{
			if(l==r)
			{
				return;
			}
			int mid=(l+r)/2;
			build(2*id+1,l,mid);
			build(2*id+2,mid+1,r);
			tree[id]=tree[2*id+1]+tree[2*id+2];
		}
		public int query(int l,int r)
		{
			return queryUtil(l,r,0,0,n-1);
		}
		private int queryUtil(int x,int y,int id,int l,int r)
		{
			if(l>y || x>r) 
				return 0;
			if(x <= l && r<=y) 
			{
				//if(!lazy[id])
					return tree[id];
				//else
				//	return tree[id][0];
			}
			int mid=l+(r-l)/2;
			shift(id);
			return queryUtil(x,y,2*id+1,l,mid)+queryUtil(x,y,2*id+2,mid+1,r);
		}
		public void update(int x,int y,int colour,int id,int l,int r)
		{
			//System.out.println(l+" "+r+" "+x);
			if(x>r || y<l)
				return;
			if(x <= l && r<=y)
			{
				
				return;
			}
			int mid=l+(r-l)/2;
			shift(id);
			update(x,y,colour,2*id+1,l,mid);
			update(x,y,colour,2*id+2,mid+1,r);
			tree[id]=tree[2*id+1]+tree[2*id+2];
		}
		public void shift(int id)
		{
			
		}
	}

	public static void fft(double[] a, double[] b, boolean invert)
	{
		int count = a.length;
		for (int i = 1, j = 0; i < count; i++) {
			int bit = count >> 1;
			for (; j >= bit; bit >>= 1) j -= bit;
			j += bit;
			if (i < j) {
				double temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				temp = b[i];
				b[i] = b[j];
				b[j] = temp;
			}
		}
		for (int len = 2; len <= count; len <<= 1) {
			int halfLen = len >> 1;
			double angle = 2 * Math.PI / len;
			if (invert) angle = -angle;
			double wLenA = Math.cos(angle), wLenB = Math.sin(angle);
			for (int i = 0; i < count; i += len) {
				double wA = 1, wB = 0;
				for (int j = 0; j < halfLen; j++) {
					double uA = a[i + j], uB = b[i + j];
					double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
					double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
					a[i + j] = uA + vA;
					b[i + j] = uB + vB;
					a[i + j + halfLen] = uA - vA;
					b[i + j + halfLen] = uB - vB;
					double nextWA = wA * wLenA - wB * wLenB;
					wB = wA * wLenB + wB * wLenA;
					wA = nextWA;
				}
			}
		}
		if (invert) {
			for (int i = 0; i < count; i++) {
				a[i] /= count;
				b[i] /= count;
			}
		}
	}
	static void multiply(long[][] a, long[][] b, long m)
	{
		int n = a.length;
		long[][] mul = new long[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				mul[i][j] = 0;
				for (int k = 0; k < n; k++)
					mul[i][j] = (mul[i][j] + (a[i][k] * b[k][j]) % m) % m;
			}
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				a[i][j] = mul[i][j];
	}

	private static long pow(long a, long b, long c)
	{
		if (b == 0)
			return 1;
		long p = pow(a, b / 2, c);
		p = (p * p) % c;
		return (b % 2 == 0) ? p : (a * p) % c;
	}

	private static long gcd(long n, long l)
	{
		if (l == 0)
			return n;
		return gcd(l, n % l);
	}
	public static void main(String[] args) throws Exception
	{
//		new Thread(null, new Runnable()
//		{
//			@Override
//			public void run()
//			{
//				/*try { 
//					InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\B-large-practice.in")); 
//				} catch (FileNotFoundException e) { // TODO Auto-generated catch block
//					e.printStackTrace(); 
//				} */
//				InputReader(System.in);
//				pw = new PrintWriter(System.out);
//				/*try { 
//					pw=new PrintWriter(new FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); 
//				} catch (FileNotFoundException e) { // TODO Auto-generated catch block
//					e.printStackTrace();
//				}*/
//				soln();
//				pw.close();
//			}
//		}, "1", 1 << 26).start();
		
		/*try { 
			InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\B-large-practice.in")); 
		} catch (FileNotFoundException e) { // TODO Auto-generated catch block
			e.printStackTrace(); 
		} */
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		/*try { 
			pw=new PrintWriter(new FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); 
		} catch (FileNotFoundException e) { // TODO Auto-generated catch block
			e.printStackTrace();
		}*/
		soln();
		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 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++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c)
	{
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private static char nextChar()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1 = (char) c;
		while (!isSpaceChar(c))
			c = read();
		return c1;
	}

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