Problem: Petya likes horse racing very much. Horses numbered from l to r take part in the races. Petya wants to evaluate the probability of victory; for some reason, to do that he needs to know the amount of nearly lucky horses' numbers. A nearly lucky number is an integer number that has at least two lucky digits the distance between which does not exceed k. Petya learned from some of his mates from Lviv that lucky digits are digits 4 and 7. The distance between the digits is the absolute difference between their positions in the number of a horse. For example, if k = 2, then numbers 412395497, 404, 4070400000070004007 are nearly lucky and numbers 4, 4123954997, 4007000040070004007 are not.

Petya prepared t intervals [li, ri] and invented number k, common for all of them. Your task is to find how many nearly happy numbers there are in each of these segments. Since the answers can be quite large, output them modulo 1000000007 (109 + 7).

Input

The first line contains two integers t and k (1 ≤ t, k ≤ 1000) — the number of segments and the distance between the numbers correspondingly. Next t lines contain pairs of integers li and ri (1 ≤ l ≤ r ≤ 101000). All numbers are given without the leading zeroes. Numbers in each line are separated by exactly one space character.

Output

Output t lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7).

Examples

Input

1 2
1 100


Output

4


Input

1 2
70 77


Output

2


Input

2 1
1 20
80 100


Output

0
0

Note

In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.

In the second sample, only 74 and 77 are in the given segment.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using vc = vector<T>;
using pii = pair<long long, long long>;
void xmax(long long& a, long long b) { a = max(a, b); }
void xmin(long long& a, long long b) { a = min(a, b); }
void print(vc<long long>& a, string second) {
  cerr << "prinitng " << second << ": ";
  for (long long i = 0; i < a.size(); i++) {
    cerr << a[i] << " ";
  }
  cerr << endl;
}
long long mod = 1e9 + 7;
long long pp(long long b, long long exp) {
  if (exp == 0) return 1;
  if (exp % 2 == 0) return pp(b * b % mod, exp / 2);
  return b * pp(b, exp - 1) % mod;
}
vc<long long> w = {7, 7, 6, 5, 5, 4, 3, 3, 2, 1, 0};
vc<long long> g = {2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0};
vc<long long> bw = {0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8};
vc<long long> bg = {0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2};
vc<vc<long long> > dp(1003, vc<long long>(1003, -2));
vc<long long> ac(1005, -3);
vc<long long> ze(1005, -4);
long long dps(long long n, long long l) {
  if (l < 0 || l > 1002 || n <= 0 || n > 1000) return 0;
  if (dp[n][l] < 0) return 0;
  return dp[n][l];
}
long long acht(long long k) {
  if (k == 0) return 1;
  if (k < 0) return 0;
  if (ac[k] < 0) return ac[k] = (acht(k - 1) * 8) % mod;
  return ac[k];
}
long long zehn(long long k) {
  if (k == 0) return 1;
  if (k < 0) return 0;
  if (ze[k] < 0) return ze[k] = (zehn(k - 1) * 10) % mod;
  return ze[k];
}
long long anz = 1001;
long long k;
vc<vc<long long> > z_a(1001, vc<long long>(1001, -2));
long long zehn_acht(long long n, long long l) {
  if (n < 0 || l < 0) return 0;
  if (z_a[n][l] >= 0) return z_a[n][l];
}
void madd(long long& a, long long b) {
  a = (a + b) % mod;
  a = (mod + a) % mod;
}
long long check_it(long long l, long long n, bool hat, long long wo) {
  if (wo == 0) return 0;
  if (hat) {
    return wo * zehn(n);
  }
  long long sum = 0;
  long long anz_norm = wo;
  long long anz_komisch = 0;
  if (wo >= 5) {
    anz_norm--;
    anz_komisch++;
  }
  if (wo >= 8) {
    anz_norm--;
    anz_komisch++;
  }
  if (l <= k) {
    madd(sum, anz_komisch * zehn(n));
  } else {
    for (long long i = 1; i <= k; i++) {
      madd(sum, anz_komisch * 2 * ((acht(i - 1) * zehn(n - i)) % mod));
    }
    madd(sum, anz_komisch * acht(k) * dps(n - k, 1002));
  }
  if (l <= k) {
    for (long long i = 1; i <= k - l; i++) {
      madd(sum, anz_norm * 2 * ((acht(i - 1) * zehn(n - i)) % mod));
    }
    madd(sum, anz_norm * (acht(k - l) * dps(n - (k - l), 1002) % mod));
  } else {
    madd(sum, anz_norm * dps(n, 1002));
  }
  return sum;
}
long long is_g(long long z) {
  vc<long long> second;
  while (z != 0) {
    long long t = z % 10;
    second.push_back(t);
    z /= 10;
  }
  long long l = k + 3;
  for (long long i = 0; i < second.size(); i++) {
    if (second[i] == 4 || second[i] == 7) {
      if (l < k) return 1;
      l = 0;
    } else {
      l++;
    }
  }
  return 0;
}
long long test(long long k) {
  long long anz = 0;
  for (long long i = 0; i < k; i++) {
    if (is_g(i)) anz++;
  }
  return anz;
}
long long find_anz(vc<char> a) {
  long long l = k + 1;
  long long sum = 0;
  bool hat = false;
  for (long long i = anz - 1; i >= 0; i--) {
    long long add = check_it(l + 1, i, hat, a[i] - '0');
    madd(sum, add);
    if (a[i] == '4' || a[i] == '7') {
      if (l < k) hat = true;
      l = 0;
    } else
      l++;
  }
  return sum;
}
long long is_good(vc<char> a) {
  long long l = k + 5;
  for (long long i = 0; i < a.size(); i++) {
    if (a[i] == '4' || a[i] == '7') {
      if (l < k) return 1;
      l = 0;
    } else {
      l++;
    }
  }
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long t;
  cin >> t >> k;
  for (long long i = 0; i < anz; i++) {
    dp[i + 1][0] = 0;
    for (long long j = 0; j < k; j++) {
      dp[i + 1][0] = (dp[i + 1][0] + acht(j) * zehn(i - j - 1) * 2) % mod;
    }
    dp[i + 1][0] = (dp[i + 1][0] + acht(k) * dps(i - k, 1002));
    dp[i + 1][1] = (2 * dps(i, 0)) % mod;
    for (long long l = 1; l < 1000; l++) {
      dp[i + 1][l + 1] = (8 * dps(i, l)) % mod;
    }
    dp[i + 1][1001] = 0;
    for (long long j = 0; j < anz; j++) {
      if (dp[i + 1][j] > 0) dp[i + 1][1001] += dp[i + 1][j];
    }
    dp[i + 1][1002] = 0;
    for (long long j = 1; j < anz; j++) {
      if (dp[i + 1][j] > 0) madd(dp[i + 1][1002], 8 * dp[i + 1][j]);
    }
    madd(dp[i + 1][1002], 2 * dp[i + 1][0]);
    dp[i + 1][1001] = (dp[i + 1][1001]) % mod;
  }
  for (long long i = 0; i < t; i++) {
    string x, y;
    cin >> x >> y;
    vc<char> a(1001, '0');
    vc<char> b(1001, '0');
    for (long long i = x.size(); i > 0; i--) {
      a[x.size() - i] = x[i - 1];
    }
    for (long long i = y.size(); i > 0; i--) {
      b[y.size() - i] = y[i - 1];
    }
    find_anz(b);
    long long tot = (find_anz(b) - find_anz(a) + is_good(b) + mod) % mod;
    cout << tot << "\n";
  }
}