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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;

int f(int num) {
	while (num > 10) {
		int tmp = 1;
		while (num > 0) {
			if (num % 10 != 0) {
				tmp *= num % 10;
			}
			num /= 10;
		}
		num = tmp;
	}
	return num;
}

int main() {
  vector<int> cnt[10];

  for (int i = 0; i < 10; ++i) {
  	cnt[i].resize(MAXN + 10, 0);
  }

  for (int num = 1; num <= MAXN; ++num) {
  	int res = f(num);
  	for (int d = 0; d < 10; ++d) {
  		cnt[d][num] = cnt[d][num - 1] + (d == res);
  	}
  }

  int q;
  cin >> q;
  for (int q_i = 0; q_i < q; ++q_i) {
  	int l, r, d;
  	cin >> l >> r >> d;
  	cout << cnt[d][r] - cnt[d][l - 1] << endl;
  }

  return 0;
}
