#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define MAX 128
#define MOD 1000000007
#define X first
#define Y second

using namespace std;

typedef long long i64;

template<typename T>
struct Matrix {
    T mat[MAX][MAX];
    static int sz, mod;

    Matrix() {}
    Matrix(const T &x) {
        int i;
        memset(mat, 0, sizeof(mat));
        for (i = 0; i < sz; ++i) mat[i][i] = x;
    }

    static int size() { return sz; }
    static void resize(int n) { sz = n; }
    static void setMod(int p) { mod = p; }

    T *operator [](int k) { return mat[k]; }
    const T *operator [](int k) const { return mat[k]; }

    Matrix operator *(const Matrix &o) const {
        Matrix ret(0);
        int i, j, k;
        for (i = 0; i < sz; ++i) {
            for (k = 0; k < sz; ++k) {
                if (!mat[i][k]) continue;
                for (j = 0; j < sz; ++j) {
                    ret.mat[i][j] += mat[i][k] * o.mat[k][j];
                    if (~mod) ret.mat[i][j] %= mod;
                }
            }
        }
        return ret;
    }

    Matrix pow(i64 n) const {
        Matrix ret(1), a = *this;
        for ( ; n; n >>= 1) {
            if (n & 1) ret = ret * a;
            a = a * a;
        }
        return ret;
    }
};

template<typename T> int Matrix<T>::sz = 77;
template<typename T> int Matrix<T>::mod = MOD;

inline int Encode(int m, int d) {
  return m * 11 + d;
}

inline void Decode(int x, int& m, int& d) {
  m = x / 11; d = x % 11;
}

i64 Calc(i64 n, int k) {
  if (n == 0) return 1;
  Matrix<i64> a = 0;
  for (int i = 0; i < 77; ++i) {
    int m, d;
    Decode(i, m, d);
    for (int j = 0; j < 11; ++j) {
      if (d != 10 && d + j == k) continue;
      if (j == 10 && d != 10) continue;
      if (j == 0 && d == 10) continue;
      int x = Encode((m * 10 + j % 10) % 7, j);
      a[x][i] = 1;
    }
  }
  a = a.pow(n - 1);
  i64 ret = 0;
  for (int i = 0; i < 11; ++i) {
    int x = Encode(0, i);
    for (int j = 1; j < 11; ++j) {
      int y = Encode(j % 10 % 7, j);
      ret = (ret + a[x][y]) % MOD;
    }
  }
  return ret;
}

int main() {
  int t, l, r, k;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &l, &r, &k);
    i64 u = Calc(l - 1, k);
    i64 v = Calc(r, k);
    i64 ans = (v - u + MOD) % MOD;
    printf("%d\n", (int)ans);
  }
  return 0;
}