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.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.OutputStream;
	import java.io.OutputStreamWriter;
	import java.io.PrintWriter;
	import java.io.Writer;
	import java.util.Arrays;
	import java.util.InputMismatchException;
	import java.util.*;
	import java.io.*;
	import java.math.*;
	public class Main51{

	static class Pair
		{ 
			int x; 
			int y;
			public Pair(int x, int y) 
			{	 
				this.x = x; 
				this.y = y; 
			}	 
		} 
		static class Compare
		{ 
			static void compare(Pair arr[], int n) 
			{ 
				// Comparator to sort the pair according to second element 
				Arrays.sort(arr, new Comparator<Pair>() { 
					@Override public int compare(Pair p1, Pair p2) 
					{ 
						if(p1.x>p2.x)
						{
							return 1;
						}
						else if(p2.x>p1.x)
						{
							return -1;
						}
						else
						{
							if(p1.y>p2.y)
							{
								return 1;
							}
							else if(p1.y<p2.y)
							{
								return -1;
							}
							else
								return 0;
						} 
					} 
				}); 
			} 
		}
		public static long pow(long a, long b)
		{
			long result=1;
			while(b>0)
			{
				if (b % 2 != 0)
				{
					result=(result*a);
					b--;
				} 
				a=(a*a);
				b /= 2;
			}   
			return result;
		}
		public static long fact(long num)
		{
					long value=1;
					int i=0;
					for(i=2;i<num;i++)
					{
						value=((value%mod)*i%mod)%mod;
					}
					return value;
				}
				public static long gcd(long a, long b)
				{
					if (a == 0)
						return b;
					return gcd(b%a, a);
				}
				
				public static long lcm(int a,int b)
				{
					return a * (b / gcd(a, b));
				}
				public static long sum(int h)
				{
					return (h*(h+1)/2);
				}
				public static int dfs(int parent,boolean[] visited)
				{
					ArrayList<Integer> arr=new ArrayList<Integer>();
					arr=graph.get(parent);
					visited[parent]=true;
					for(int i=0;i<arr.size();i++)
					{
						int num=arr.get(i);
						if(visited[num]==false)
						{
							if(color[parent]!=c[num])
							{
								color[num]=c[num];
								count++;
							}
							else
							{
								color[num]=c[num];
							}
							dfs(num,visited);
						}
					}
					return count;
				}
				static int[] c;
				static int count=0;
				static int f=0;
				static char[] ch;
				static long mod=1000000007L;
				static ArrayList<ArrayList<Integer>> graph;
				static int[] color;
				public static void main(String args[])throws IOException
				{
				//	InputReader in=new InputReader(System.in);
				//	OutputWriter out=new OutputWriter(System.out);
				//	long a=pow(26,1000000005);
				    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
					ArrayList<Integer> ar=new ArrayList<>();
					ArrayList<Integer> ar1=new ArrayList<>();
					ArrayList<Integer> ar2=new ArrayList<>();
					ArrayList<Integer> ar3=new ArrayList<>();
					ArrayList<Integer> ar4=new ArrayList<>();
					TreeSet<Integer> ts=new TreeSet<>();
					TreeSet<Integer> ts1=new TreeSet<>();
					TreeSet<String> pre=new TreeSet<>();
				//	HashMap<Integer,Integer> hash=new HashMap<>();
					//HashMap<Long,Integer> hash1=new HashMap<Long,Integer>();
					HashMap<Long,Integer> hash2=new HashMap<Long,Integer>();
				/*	boolean[] prime=new boolean[10001];
					for(int i=2;i*i<=10000;i++)
					{
						if(prime[i]==false)
						{
							for(int j=2*i;j<=10000;j+=i)
							{
								prime[j]=true;
								
							}
						}
					}*/
					int[][] count=new int[1000001][10];
					for(int i=1;i<1000001;i++)
					{
						for(int j=1;j<=9;j++)
						{
							count[i][j]=count[i-1][j];
						}
						if(i<10)
						{
							count[i][i]++;
						}
						else
						{
							int flag=1;
							int ans=i;
							while(flag==1)
							{
								int ans1=1;
								String s=ans+"";
								for(int j=0;j<s.length();j++)
								{
									if(s.charAt(j)!='0')
									{
										ans1=ans1*(s.charAt(j)-'0');
									}
								}
								ans=ans1;
								if(ans<10)
								{
									flag=0;
									break;
								}
							}
							count[i][ans]++;
						}
					}
					int q=i();
					while(q-->0)
					{
						int l=i();
						int r=i();
						int k=i();
						int ans2=count[r][k]-count[l-1][k];
						pln(ans2+"");
					}
				}
	
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				/**/
				static InputReader in=new InputReader(System.in);
					static OutputWriter out=new OutputWriter(System.out);
					public static long l()
					{
						String s=in.String();
						return Long.parseLong(s);
					}
					public static void pln(String value)
					{
						System.out.println(value);
					}
					public static int i()
					{
						return in.Int();
					}
					public static String s()
					{
						return in.String();
					}
		}
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			class InputReader {
				 
				private InputStream stream;
				private byte[] buf = new byte[1024];
				private int curChar;
				private int numChars;
				private SpaceCharFilter filter;
			 
				public InputReader(InputStream stream) {
					this.stream = stream;
				}
			 
				public 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++];
				}
			 
				public int Int() {
					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;
				}
			 
				public String String() {
					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 boolean isSpaceChar(int c) {
					if (filter != null)
						return filter.isSpaceChar(c);
					return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
				}
			 
				public String next() {
					return String();
				}
			 
				public interface SpaceCharFilter {
					public boolean isSpaceChar(int ch);
				}
			}
			 
			class OutputWriter {
				private final PrintWriter writer;
			 
				public OutputWriter(OutputStream outputStream) {
					writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
				}
			 
				public OutputWriter(Writer writer) {
					this.writer = new PrintWriter(writer);
				}
			 
				public void print(Object...objects) {
					for (int i = 0; i < objects.length; i++) {
						if (i != 0)
							writer.print(' ');
						writer.print(objects[i]);
					}
				}
			 
				public void printLine(Object...objects) {
					print(objects);
					writer.println();
				}
			 
				public void close() {
					writer.close();
				}
			 
				public void flush() {
					writer.flush();
				}
			 
				}
			 
				class IOUtils {
			 
				public static int[] readIntArray(InputReader in, int size) {
					int[] array = new int[size];
					for (int i = 0; i < size; i++)
						array[i] = in.Int();
					return array;
				}
			 
				}