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.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.InputMismatchException;
					public class Solution1 implements Runnable
					{
						static final long MAX = 1000000007L;
						static class InputReader
						{
							private InputStream stream;
							private byte[] buf = new byte[1024];
							private int curChar;
							private int numChars;
							private SpaceCharFilter filter;
							private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
					 
							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 String nextLine()
							{
								String str = "";
					            try
					            {
					                str = br.readLine();
					            }
					            catch (IOException e)
					            {
					                e.printStackTrace();
					            }
					            return str;
							}
							public 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;
							}
							
							public 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;
							}
							
							public double nextDouble() 
							{
								int c = read();
								while (isSpaceChar(c))
									c = read();
								int sgn = 1;
								if (c == '-') 
								{
									sgn = -1;
									c = read();
								}
								double res = 0;
								while (!isSpaceChar(c) && c != '.') 
								{
									if (c == 'e' || c == 'E')
										return res * Math.pow(10, nextInt());
									if (c < '0' || c > '9')
										throw new InputMismatchException();
									res *= 10;
									res += c - '0';
									c = read();
								}
								if (c == '.') 
								{
									c = read();
									double m = 1;
									while (!isSpaceChar(c)) 
									{
										if (c == 'e' || c == 'E')
											return res * Math.pow(10, nextInt());
										if (c < '0' || c > '9')
											throw new InputMismatchException();
										m /= 10;
										res += (c - '0') * m;
										c = read();
									}
								}
								return res * sgn;
							}
							
							public String readString() 
							{
								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 readString();
							}
							
							public interface SpaceCharFilter 
							{
								public boolean isSpaceChar(int ch);
							}
						}
					 	
						public static void main(String args[]) throws Exception
						{
							new Thread(null, new Solution1(),"Solution1",1<<26).start();
						}
						public static int gcd(int a, int b)
					    {
					        if (a == 0)
					            return b;
					         
					        return gcd(b%a, a);
					    }	
						 
						  static int lcm(int a, int b)
						    {
						        return (a*b)/gcd(a, b);
						    }
						static int max=  -1;
						
					
						public void run()
						{
							InputReader sc= new InputReader(System.in);
							PrintWriter w= new PrintWriter(System.out);
							int[] ans = new int[1000001];
							for(int i = 0;i < 10;i++){
								ans[i] = i;
							}
							for(int i = 10;i < ans.length;i++){
								ans[i] = ans(i);
							}
							
							int[][] e = new int[1000001][10];
							for(int i = 1;i < 1000001;i++){
								ans[i] = ans[ans[i]];
								for(int j = 0;j <= 9;j++){
									if(ans[i] == j){		
										e[i][j] = e[i-1][j] + 1;
									}else{
										e[i][j] = e[i-1][j];
									}
								}
							}
							int q = sc.nextInt();
							for(int i = 0;i < q;i++){
								int l = sc.nextInt();
								int r = sc.nextInt();
								int k = sc.nextInt();
								w.println(e[r][k] - e[l-1][k]);
							}
							w.close();
						}
						public int ans(int x){
							int an = 1;
							while(x != 0){
								if(x % 10 == 0){
									x = x/10;
									continue;
								}
								an *= (x % 10);
								x = x/10;
							}
							return an;
						}
						public static long gcd(long a,long b)
					    {
					        if (a == 0)
					            return b;
					         
					        return gcd(b%a, a);
					    } 
						    // method to return LCM of two numbers
						    static long lcm(long a, long b)
						    {
						        return (a*b)/gcd(a, b);
						    }
						
						ArrayList<Integer> p = new ArrayList(); 
						boolean[] prime;
						 void sieveOfEratosthenes(int n)
						    {
						        // Create a boolean array "prime[0..n]" and initialize
						        // all entries it as true. A value in prime[i] will
						        // finally be false if i is Not a prime, else true.
						        prime = new boolean[n+1];
						        for(int i=0;i<n;i++)
						            prime[i] = true;
						         
						        for(int p = 2; p*p <=n; p++)
						        {
						            // If prime[p] is not changed, then it is a prime
						            if(prime[p] == true)
						            {
						                // Update all multiples of p
						                for(int i = p*2; i <= n; i += p)
						                    prime[i] = false;
						            }
						        }
						         
						        // Print all prime numbers
						        for(int i = 2; i <= n; i++)
						        {
						            if(prime[i] == true)
						                p.add(i);
						        }
						    }
						     
		static class Pair implements Comparable<Pair>{
								int a;
								int b;	
								
								Pair(int a,int b)	{
									this.a = a;
									this.b = b;
									
								}
								public boolean equals(Object o)
								{
									Pair p = (Pair)o;
									return (p.a==a && p.b==b) || (p.b == a && p.a == b);
								}
								public int compareTo(Pair p){
									if(p.b == this.b)
										return Integer.compare(this.a,p.a);
									return Integer.compare(this.b,p.b);
								}
								public int hashCode()
								{
									return new Long(a).hashCode()*31 + new Long(a).hashCode();
								}
						}
					}