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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct all {
  int zer, one, two, thr, fou, fiv, six, sev, eig, nin;
  all() {
    zer = 0, one = 0;
    two = 0;
    thr = 0;
    fou = 0;
    fiv = 0;
    six = 0;
    sev = 0;
    eig = 0;
    nin = 0;
  }
  all(int a0, int a1, int a2, int a3, int a4, int a5, int a6, int a7, int a8,
      int a9) {
    zer = a0, one = a1;
    two = a2;
    thr = a3;
    fou = a4;
    fiv = a5;
    six = a6;
    sev = a7;
    eig = a8;
    nin = a9;
  }
};
int brr[1000000 + 5];
all seg[4 * 1000000 + 5];
void makeSegment(int node, int s, int f) {
  if (s == f) {
    if (brr[s] == 0)
      seg[node] = all(1, 0, 0, 0, 0, 0, 0, 0, 0, 0);
    else if (brr[s] == 1)
      seg[node] = all(0, 1, 0, 0, 0, 0, 0, 0, 0, 0);
    else if (brr[s] == 2)
      seg[node] = all(0, 0, 1, 0, 0, 0, 0, 0, 0, 0);
    else if (brr[s] == 3)
      seg[node] = all(0, 0, 0, 1, 0, 0, 0, 0, 0, 0);
    else if (brr[s] == 4)
      seg[node] = all(0, 0, 0, 0, 1, 0, 0, 0, 0, 0);
    else if (brr[s] == 5)
      seg[node] = all(0, 0, 0, 0, 0, 1, 0, 0, 0, 0);
    else if (brr[s] == 6)
      seg[node] = all(0, 0, 0, 0, 0, 0, 1, 0, 0, 0);
    else if (brr[s] == 7)
      seg[node] = all(0, 0, 0, 0, 0, 0, 0, 1, 0, 0);
    else if (brr[s] == 8)
      seg[node] = all(0, 0, 0, 0, 0, 0, 0, 0, 1, 0);
    else if (brr[s] == 9)
      seg[node] = all(0, 0, 0, 0, 0, 0, 0, 0, 0, 1);
  } else {
    int m = (s + f) / 2;
    makeSegment(2 * node, s, m);
    makeSegment(2 * node + 1, m + 1, f);
    seg[node].zer = seg[2 * node].zer + seg[2 * node + 1].zer;
    seg[node].one = seg[2 * node].one + seg[2 * node + 1].one;
    seg[node].two = seg[2 * node].two + seg[2 * node + 1].two;
    seg[node].thr = seg[2 * node].thr + seg[2 * node + 1].thr;
    seg[node].fou = seg[2 * node].fou + seg[2 * node + 1].fou;
    seg[node].fiv = seg[2 * node].fiv + seg[2 * node + 1].fiv;
    seg[node].six = seg[2 * node].six + seg[2 * node + 1].six;
    seg[node].sev = seg[2 * node].sev + seg[2 * node + 1].sev;
    seg[node].eig = seg[2 * node].eig + seg[2 * node + 1].eig;
    seg[node].nin = seg[2 * node].nin + seg[2 * node + 1].nin;
  }
}
all query(int node, int s, int f, int l, int r) {
  if (s > r || f < l)
    return all(0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
  else if (l <= s && r >= f)
    return seg[node];
  else {
    int mid = (s + f) / 2;
    all a1 = query(2 * node, s, mid, l, r);
    all a2 = query(2 * node + 1, mid + 1, f, l, r);
    all a3;
    a3.zer = a1.zer + a2.zer;
    a3.one = a1.one + a2.one;
    a3.two = a1.two + a2.two;
    a3.thr = a1.thr + a2.thr;
    a3.fou = a1.fou + a2.fou;
    a3.fiv = a1.fiv + a2.fiv;
    a3.six = a1.six + a2.six;
    a3.sev = a1.sev + a2.sev;
    a3.eig = a1.eig + a2.eig;
    a3.nin = a1.nin + a2.nin;
    return a3;
  }
}
void fill(int n) {
  for (int i = 1; i <= n; i++) {
    if (i < 10)
      brr[i] = i;
    else {
      int j = i;
      int k = 1;
      while (j != 0) {
        int dig = j % 10;
        if (dig != 0) k *= dig;
        j /= 10;
      }
      brr[i] = brr[k];
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q;
  cin >> q;
  fill(1000000 + 1);
  makeSegment(1, 1, 1000000);
  for (int i = 1; i <= q; i++) {
    int x, y, t;
    cin >> x >> y >> t;
    all ans = query(1, 1, 1000000, x, y);
    if (t == 0)
      cout << ans.zer << '\n';
    else if (t == 1)
      cout << ans.one << '\n';
    else if (t == 2)
      cout << ans.two << '\n';
    else if (t == 3)
      cout << ans.thr << '\n';
    else if (t == 4)
      cout << ans.fou << '\n';
    else if (t == 5)
      cout << ans.fiv << '\n';
    else if (t == 6)
      cout << ans.six << '\n';
    else if (t == 7)
      cout << ans.sev << '\n';
    else if (t == 8)
      cout << ans.eig << '\n';
    else if (t == 9)
      cout << ans.nin << '\n';
  }
}