#include <bits/stdc++.h>   using namespace std;   void upd(long long &x, long long y) { x += y; }   struct node {     int nxt;     long long sta, v[10];     node() {       nxt = 0;       memset(v, 0, sizeof(v));     }   };   struct state {     vector<node> nodes;     int head[100007];     state() { memset(head, -1, sizeof(head)); }     size_t size() const { return nodes.size(); }     void sum() {       for (int i = 0; i < nodes.size(); i++)         for (int j = 1; j <= 9; j++) upd(nodes[i].v[j], nodes[i].v[j - 1]);     }     void update(int at, long long key, long long v) {       int tmp = key % 100007;       for (int i = head[tmp]; i != -1; i = nodes[i].nxt)         if (nodes[i].sta == key) {           upd(nodes[i].v[at], v);           return;         }       node now;       now.nxt = head[tmp];       head[tmp] = nodes.size();       now.v[at] = v;       now.sta = key;       nodes.push_back(now);     }     long long find(int at, long long key) {       int tmp = key % 100007;       for (int i = head[tmp]; i != -1; i = nodes[i].nxt)         if (nodes[i].sta == key) return nodes[i].v[at];       return 0;     }   } f[11][20];   long long c[2][20], bit[15];   bitset<200> vis[15], pre[200], tmp;   struct big {     int a[35], len;     void read() {       memset(a, 0, sizeof(a));       len = 0;       char ch = getchar();       for (; ch <  0  || ch >  9 ; ch = getchar())         ;       for (; ch >=  0  && ch <=  9 ; ch = getchar()) a[len++] = ch - 48;     }     long long mod() {       long long ans = 0;       for (int i = 0; i < len; i++)         ans = (10ll * ans + a[i]) % 1000000000000000007ll;       return ans;     }     void plus() {       a[len - 1]++;       for (int i = len - 1; i >= 1; i--) a[i - 1] += a[i] / 10, a[i] %= 10;       if (a[0] > 9) {         a[0] = 1;         for (int i = 1; i <= len; i++) a[i] = 0;         len++;       }     }   } L, R;   int sum[40], times = 0;   void dfs(int dep, int cnt, int sum, long long msk) {     int mx = sum + (18 - cnt) * 9;     tmp = pre[mx >> 1];     if (sum >> 1) tmp ^= pre[(sum >> 1) - 1];     if ((vis[dep - 1] & tmp) == tmp) return;     if (dep == 10) {       for (int i = sum >> 1; i >= 0; i--)         if (vis[dep - 1][i]) {           int dif = sum - i - i;           if (dif > 1) {             ::sum[cnt]++;             f[dif][0].update(0, msk, 1);           }           break;         }       return;     }     vis[dep] = vis[dep - 1];     dfs(dep + 1, cnt, sum, msk);     for (; cnt < 18;) {       vis[dep] |= vis[dep] << dep;       dfs(dep + 1, ++cnt, sum += dep, msk += bit[dep]);     }   }   long long solve(int dif, big lim) {     long long ans = 0, msk = 0;     int len = lim.len;     state *F = f[dif];     for (int i = 0; i < len; i++)       if (len - i > 18) {         for (int j = 0; j < lim.a[i]; j++) ans += F[len - i - 1].find(9, msk);       } else if (lim.a[i]) {         ans += F[len - i].find(lim.a[i] - 1, msk);         msk += bit[lim.a[i]];       }     return ans;   }   long long solve2(big lim) {     int len = lim.len;     long long ans = 0;     int part = 0;     for (int i = 0; i < len; i++) {       int odd = lim.a[i] >> 1, even = lim.a[i] - odd;       ans += c[part][len - 1 - i] * odd + c[part ^ 1][len - 1 - i] * even;       part ^= lim.a[i] & 1;     }     return ans;   }   inline long long read() {     long long x = 0;     char ch = getchar();     for (; ch <  0  || ch >  9 ; ch = getchar())       ;     for (; ch >=  0  && ch <=  9 ; ch = getchar()) x = x * 10 - 48 + ch;     return x;   }   int main() {     pre[0][0] = 1;     for (int i = 1; i <= 190; i++) pre[i] = pre[i - 1], pre[i][i] = 1;     c[0][0] = 1;     for (int i = 1; i <= 18; i++)       c[0][i] = c[1][i] =           5ll * (c[0][i - 1] + c[1][i - 1]) % 1000000000000000007ll;     bit[1] = 1;     for (int i = 2; i < 10; i++) bit[i] = bit[i - 1] << 5;     vis[0].set(0);     dfs(1, 0, 0, 0);     for (int i = 2; i < 10; i++) {       f[i][0].sum();       for (int j = 0; j < 18; j++) {         state &cur = f[i][j], &nxt = f[i][j + 1];         for (int id = 0, sz = cur.size(); id < sz; id++) {           int cnt = j;           long long way = cur.nodes[id].v[9];           long long msk = cur.nodes[id].sta, tmp = msk;           for (int k = 1; k < 10; k++, tmp >>= 5) {             int rem = tmp & 31;             if (!rem) continue;             cnt += rem;             nxt.update(k, msk - bit[k], way);           }           if (cnt < 18) nxt.update(0, msk, way);         }         nxt.sum();       }     }     int Q = read();     while (Q--) {       L.read();       R.read();       R.plus();       int k = read();       long long ans = R.mod() - L.mod();       if (!k) {         ans -= solve2(R) - solve2(L);         for (int i = 2; i < 10; i += 2) ans -= solve(i, R) - solve(i, L);       } else         for (int i = k + 1; i < 10; i++) ans -= solve(i, R) - solve(i, L);       printf( %lld n , (ans % 1000000000000000007ll + 1000000000000000007ll) %                            1000000000000000007ll);     }     return 0;   }   