Let us define two functions *f* and *g* on positive integer numbers. 

<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/120df92771639f1f51a4b216dccd3ed7c32bb859.png" style="max-width: 100.0%;max-height: 100.0%;"/> 

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*.
The first line of the input contains an integer *Q* (1 ≤ *Q* ≤ 2 × 10<sup class="upper-index">5</sup>) representing the number of queries. 

*Q* lines follow, each of which contains 3 integers *l*, *r* and *k* (1 ≤ *l* ≤ *r* ≤ 10<sup class="upper-index">6</sup>, 1 ≤ *k* ≤ 9).
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
4
22 73 9
45 64 6
47 55 7
2 62 4
1
4
0
8
4
82 94 6
56 67 4
28 59 9
39 74 4
3
1
1
5
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B {

	static final int MAX = 1000000;
	static final int[] fMap = new int[MAX+1];
	static final int[] indexTotal = new int[10];
	static int[][] countBig = new int[10][MAX+1]; 
	
	public static void main(String[] args) throws IOException {

		for (int i = 1; i <= MAX; i++) {
			if (i < 10) {
				fMap[i] = i;
				indexTotal[i]++;
			} else {
				fMap[i] = fMap[f(i)];
				indexTotal[fMap[f(i)]]++;
			}
			for (int j = 1; j < indexTotal.length; j++) {
				countBig[j][i] = indexTotal[j];
			}
		}
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer out = new StringBuffer();

		int l, r, k;
		String[] line;
		int q = Integer.parseInt(in.readLine());
		for (int i = 0; i < q; i++) {
			line = in.readLine().split(" ");
			l = Integer.parseInt(line[0]);
			r = Integer.parseInt(line[1]);
			k = Integer.parseInt(line[2]);

			out.append(countBig[k][r] - countBig[k][l-1]);
			out.append("\n");
		}
		System.out.print(out);
	}
	
	static int f(int n) {
		String num = Integer.toString(n);
		int result = 0;
		char c;
		int temp;
		for (int i = 0; i < num.length(); i++) {
			c = num.charAt(i);
			temp = Integer.valueOf(c)-48;
			if (temp != 0) {
				if (result == 0) {
					result = temp;
				} else {
					result *= temp;
				}
			}
		}
		return result;
	}
}