#include <bits/stdc++.h>
using namespace std;
int sum;
vector<long long> vec[11];
const int moo = 100017;
struct Hashset {
  long long key[40005];
  long long val[40005];
  int nxt[40005];
  int head[moo], nd;
  long long &operator[](const long long &x) {
    for (int i = head[x % moo]; i; i = nxt[i])
      if (key[i] == x) return val[i];
    key[++nd] = x;
    nxt[nd] = head[x % moo];
    head[x % moo] = nd;
    return val[nd];
  }
  long long findv(const long long &x) const {
    for (int i = head[x % moo]; i; i = nxt[i])
      if (key[i] == x) return val[i];
    return 0;
  }
} vf[20][11];
void dfs(int x, int y, int s, long long st, bitset<100> S) {
  if (!S[s / 2]) {
    int p = s / 2;
    for (; !S[p]; --p)
      ;
    vec[s - p * 2].push_back(st);
  }
  if (x > 18) return;
  int pl = s / 2, pr = s / 2;
  for (; pl >= 0 && S[pl]; --pl)
    ;
  for (; pr < 100 && S[pr]; ++pr)
    ;
  if (pr - pl - 1 >= 9) return;
  for (int i = y; i <= 9; i++)
    dfs(x + 1, i, s + i, st + (1ll << (5 * i)), S | (S << i));
}
void init() {
  bitset<100> S;
  S[0] = 1;
  dfs(1, 1, 0, 0, S);
  for (int i = (int)(2); i <= (int)(9); i++) {
    sort(vec[i].begin(), vec[i].end());
    for (auto j : vec[i]) ++vf[0][i][j];
  }
  for (int i = (int)(1); i <= (int)(18); i++)
    for (int j = (int)(2); j <= (int)(9); j++)
      for (int p = (int)(1); p <= (int)(vf[i - 1][j].nd); p++) {
        pair<long long, long long> k(vf[i - 1][j].key[p], vf[i - 1][j].val[p]);
        vf[i][j][k.first] += k.second;
        for (int l = (int)(1); l <= (int)(9); l++)
          if ((k.first >> (5 * l)) & 31)
            vf[i][j][k.first - (1ll << (5 * l))] += k.second;
      }
}
long long FFF(int i, long long j, int k) { return vf[i][k].findv(j); }
long long FF(long long l, int k) {
  if (l % 2 == 1) return (l + 1) / 2;
  int tmp = 0;
  for (long long x = l; x; tmp += x % 10, x /= 10)
    ;
  return (l + 1) / 2 + (tmp % 2 == k);
}
long long F(long long l, int k) {
  static int a[20], top;
  l++;
  for (top = 0; l; a[++top] = l % 10, l /= 10)
    ;
  long long st = 0, ans = 0;
  for (int i = (int)(top); i >= (int)(1); i--) {
    for (int j = (int)(0); j <= (int)(a[i] - 1); j++)
      ans += FFF(i - 1, st + (j ? 1ll << (5 * j) : 0), k);
    if (a[i]) st += 1ll << (5 * a[i]);
  }
  return ans;
}
int main() {
  init();
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    long long l, r, k, ans = 0;
    scanf("%lld%lld%lld", &l, &r, &k);
    if (k == 0) {
      ans = FF(r, 0) - FF(l - 1, 0);
      for (k += 2; k <= 9; k += 2) ans -= F(r, k) - F(l - 1, k);
    } else {
      ans = r - l + 1;
      for (k++; k <= 9; k++) ans -= F(r, k) - F(l - 1, k);
    }
    printf("%lld\n", ans);
  }
}
