#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll md = 1000000007;
vector<ll> p, B, fac(2, 1), ifac(2, 1);
ll ad(ll a, ll b, ll mod = md) { return (a % mod + b % mod + mod) % mod; }
ll ml(ll a, ll b, ll mod = md) { return ((a % mod) * (b % mod)) % mod; }
ll fn(ll a, ll r, ll n, ll mod = md) {
  ll res = 1, ans = 0;
  r %= mod;
  if (r < 0) r += mod;
  while (n) {
    if (n & 1) ans = (r * ans + res) % mod;
    res = (res * r + res) % mod;
    r = (r * r) % mod;
    n = n / 2;
  }
  ans = (ans * a) % mod;
  if (ans < 0) ans += md;
  return ans;
}
ll pw(ll x, ll n, ll mod = md) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1) res = (res * x) % mod;
    n = (n >> 1);
    x = (x * x) % mod;
  }
  return res;
}
void cachefact(ll lim, ll mod = md) {
  for (int i = 2; i <= lim; i++) {
    ifac.push_back((ifac[mod % i] * (mod - mod / i) % mod) % mod);
  }
  for (ll i = 2; i <= lim; i++) {
    fac.push_back((fac[i - 1] * i) % mod);
    ifac[i] = (ifac[i - 1] * ifac[i]) % mod;
  }
}
ll C(int n, int r) {
  if (n < r || r < 0) return 0;
  return ml(fac[n], ml(ifac[r], ifac[n - r]));
}
ll P(int n, int r) {
  if (n < r) return 0;
  return ml(fac[n], ifac[n - r]);
}
void sieve(ll n) {
  vector<bool> prime(n + 1, true);
  for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
      for (int j = 2 * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  p.push_back(2);
  for (int i = 3; i <= n; i += 2) {
    if (prime[i]) p.push_back(i);
  }
}
ll Phi(ll n) {
  ll res = n;
  for (int i = 0; p[i] * p[i] <= n; i++) {
    short cnt = 0;
    while (n % p[i] == 0) {
      n /= p[i];
      cnt++;
    }
    if (cnt) res -= (res / p[i]);
  }
  if (n > 1) res -= (res / n);
  return res;
}
void sieveGCD(ll lim, vector<ll> &tab) {
  int pn = p.size();
  for (int i = 1; i <= lim; i++) tab[i] = i;
  for (int i = 0; i < pn && p[i] <= lim; i++) {
    for (int j = p[i]; j <= lim; j += p[i]) {
      tab[j] = (tab[j] / p[i]) * (p[i] - 1);
    }
  }
}
void sieveMU(ll n, vector<ll> &mu) {
  vector<ll> factor(n + 1, 0);
  for (int i = 2; i * i <= n; i++) {
    if (!factor[i]) {
      for (int j = i * i; j <= n; j += i) factor[j] = i;
    }
  }
  mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!factor[i]) {
      mu[i] = -1;
      continue;
    }
    if ((i / factor[i]) % factor[i] == 0) {
      mu[i] = 0;
    } else {
      mu[i] = (-1) * mu[i / factor[i]];
    }
  }
}
ll extended_euclid(ll a, ll b, ll *x, ll *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  ll x1, y1;
  ll gcd = extended_euclid(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
ll crt(vector<pair<ll, ll>> &a, int an, ll m) {
  ll ret = 0;
  for (int i = 0; i < an; i++) {
    ll p = m / a[i].second, q = a[i].second, r, s;
    int g = extended_euclid(p, q, &r, &s);
    ret = ad(ret, ml(a[i].first, ml(r, p, m), m), m);
  }
  return ret;
}
void bernoulli() {
  B = {1,         500000003, 166666668, 0, 766666672, 0, 23809524,  0,
       766666672, 0,         348484851, 0, 469963373, 0, 166666669, 0,
       413725486, 0,         865914848, 0, 948484326, 0, 427542427, 0,
       469876793, 0,         168092185, 0, 980747753, 0, 678176322, 0,
       297409831, 0,         781306726, 0, 35337905,  0, 482221937, 0,
       83084250,  0,         310292012, 0, 334581823, 0, 437628892, 0,
       708314481, 0,         860344292, 0, 643009310, 0, 159517512, 0,
       742356578, 0,         392872747, 0, 465850017, 0, 647900229, 0,
       431346688, 0,         461733065, 0, 255588829, 0, 307276324, 0,
       610411531, 0,         197137262, 0, 18565655,  0, 852238879, 0,
       284923925, 0,         483196916, 0, 208794235, 0, 148591948, 0,
       244784253, 0,         416223553, 0, 138705149, 0, 711847843, 0,
       394739272, 0,         39530788,  0, 94103270};
}
void multiply(vector<vector<ll>> &F, vector<vector<ll>> &R, ll N) {
  vector<vector<ll>> temp(N, vector<ll>(N, 0));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        temp[i][j] = ad(temp[i][j], ml(F[i][k], R[k][j]));
      }
    }
  }
  F = temp;
}
void mpow(vector<vector<ll>> &F, ll N, ll n) {
  vector<vector<ll>> res(N, vector<ll>(N, 0));
  for (int i = 0; i < N; i++) res[i][i] = 1;
  while (n) {
    if (n & 1) multiply(res, F, N);
    multiply(F, F, N);
    n >>= 1;
  }
  F = res;
}
ll dp[100][4];
ll F(ll n) {
  ll d[21];
  ll answer = 0, c = 0, nums = 3;
  while (n) {
    d[c++] = n % 10;
    n /= 10;
  }
  for (int i = c - 1; i >= 0; i--) {
    if (nums == 0) break;
    if (d[i] != 0) {
      answer += dp[i][nums] + (d[i] - 1) * dp[i][--nums];
    }
  }
  return answer;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cachefact(31);
  for (int i = 0; i <= 30; i++) {
    dp[i][0] = 1;
    dp[i][1] = 1 + i * 9;
    dp[i][2] = 1 + i * 9 + C(i, 2) * 81;
    dp[i][3] = 1 + i * 9 + C(i, 2) * 81 + C(i, 3) * 729;
  }
  int t;
  cin >> t;
  while (t--) {
    ll L, R;
    cin >> L >> R;
    cout << F(R) - F(L - 1) << "\n";
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

Let's call some positive integer classy if its decimal representation contains no more than 3 non-zero digits. For example, numbers 4, 200000, 10203 are classy and numbers 4231, 102306, 7277420000 are not.

You are given a segment [L; R]. Count the number of classy integers x such that L ≤ x ≤ R.

Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^4) — the number of segments in a testcase.

Each of the next T lines contains two integers L_i and R_i (1 ≤ L_i ≤ R_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of classy integers on a segment [L_i; R_i].

Example

Input

4
1 1000
1024 1024
65536 65536
999999 1000001


Output

1000
1
0
2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll md = 1000000007;
vector<ll> p, B, fac(2, 1), ifac(2, 1);
ll ad(ll a, ll b, ll mod = md) { return (a % mod + b % mod + mod) % mod; }
ll ml(ll a, ll b, ll mod = md) { return ((a % mod) * (b % mod)) % mod; }
ll fn(ll a, ll r, ll n, ll mod = md) {
  ll res = 1, ans = 0;
  r %= mod;
  if (r < 0) r += mod;
  while (n) {
    if (n & 1) ans = (r * ans + res) % mod;
    res = (res * r + res) % mod;
    r = (r * r) % mod;
    n = n / 2;
  }
  ans = (ans * a) % mod;
  if (ans < 0) ans += md;
  return ans;
}
ll pw(ll x, ll n, ll mod = md) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1) res = (res * x) % mod;
    n = (n >> 1);
    x = (x * x) % mod;
  }
  return res;
}
void cachefact(ll lim, ll mod = md) {
  for (int i = 2; i <= lim; i++) {
    ifac.push_back((ifac[mod % i] * (mod - mod / i) % mod) % mod);
  }
  for (ll i = 2; i <= lim; i++) {
    fac.push_back((fac[i - 1] * i) % mod);
    ifac[i] = (ifac[i - 1] * ifac[i]) % mod;
  }
}
ll C(int n, int r) {
  if (n < r || r < 0) return 0;
  return ml(fac[n], ml(ifac[r], ifac[n - r]));
}
ll P(int n, int r) {
  if (n < r) return 0;
  return ml(fac[n], ifac[n - r]);
}
void sieve(ll n) {
  vector<bool> prime(n + 1, true);
  for (int i = 2; i * i <= n; i++) {
    if (prime[i]) {
      for (int j = 2 * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  p.push_back(2);
  for (int i = 3; i <= n; i += 2) {
    if (prime[i]) p.push_back(i);
  }
}
ll Phi(ll n) {
  ll res = n;
  for (int i = 0; p[i] * p[i] <= n; i++) {
    short cnt = 0;
    while (n % p[i] == 0) {
      n /= p[i];
      cnt++;
    }
    if (cnt) res -= (res / p[i]);
  }
  if (n > 1) res -= (res / n);
  return res;
}
void sieveGCD(ll lim, vector<ll> &tab) {
  int pn = p.size();
  for (int i = 1; i <= lim; i++) tab[i] = i;
  for (int i = 0; i < pn && p[i] <= lim; i++) {
    for (int j = p[i]; j <= lim; j += p[i]) {
      tab[j] = (tab[j] / p[i]) * (p[i] - 1);
    }
  }
}
void sieveMU(ll n, vector<ll> &mu) {
  vector<ll> factor(n + 1, 0);
  for (int i = 2; i * i <= n; i++) {
    if (!factor[i]) {
      for (int j = i * i; j <= n; j += i) factor[j] = i;
    }
  }
  mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!factor[i]) {
      mu[i] = -1;
      continue;
    }
    if ((i / factor[i]) % factor[i] == 0) {
      mu[i] = 0;
    } else {
      mu[i] = (-1) * mu[i / factor[i]];
    }
  }
}
ll extended_euclid(ll a, ll b, ll *x, ll *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  ll x1, y1;
  ll gcd = extended_euclid(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
ll crt(vector<pair<ll, ll>> &a, int an, ll m) {
  ll ret = 0;
  for (int i = 0; i < an; i++) {
    ll p = m / a[i].second, q = a[i].second, r, s;
    int g = extended_euclid(p, q, &r, &s);
    ret = ad(ret, ml(a[i].first, ml(r, p, m), m), m);
  }
  return ret;
}
void bernoulli() {
  B = {1,         500000003, 166666668, 0, 766666672, 0, 23809524,  0,
       766666672, 0,         348484851, 0, 469963373, 0, 166666669, 0,
       413725486, 0,         865914848, 0, 948484326, 0, 427542427, 0,
       469876793, 0,         168092185, 0, 980747753, 0, 678176322, 0,
       297409831, 0,         781306726, 0, 35337905,  0, 482221937, 0,
       83084250,  0,         310292012, 0, 334581823, 0, 437628892, 0,
       708314481, 0,         860344292, 0, 643009310, 0, 159517512, 0,
       742356578, 0,         392872747, 0, 465850017, 0, 647900229, 0,
       431346688, 0,         461733065, 0, 255588829, 0, 307276324, 0,
       610411531, 0,         197137262, 0, 18565655,  0, 852238879, 0,
       284923925, 0,         483196916, 0, 208794235, 0, 148591948, 0,
       244784253, 0,         416223553, 0, 138705149, 0, 711847843, 0,
       394739272, 0,         39530788,  0, 94103270};
}
void multiply(vector<vector<ll>> &F, vector<vector<ll>> &R, ll N) {
  vector<vector<ll>> temp(N, vector<ll>(N, 0));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        temp[i][j] = ad(temp[i][j], ml(F[i][k], R[k][j]));
      }
    }
  }
  F = temp;
}
void mpow(vector<vector<ll>> &F, ll N, ll n) {
  vector<vector<ll>> res(N, vector<ll>(N, 0));
  for (int i = 0; i < N; i++) res[i][i] = 1;
  while (n) {
    if (n & 1) multiply(res, F, N);
    multiply(F, F, N);
    n >>= 1;
  }
  F = res;
}
ll dp[100][4];
ll F(ll n) {
  ll d[21];
  ll answer = 0, c = 0, nums = 3;
  while (n) {
    d[c++] = n % 10;
    n /= 10;
  }
  for (int i = c - 1; i >= 0; i--) {
    if (nums == 0) break;
    if (d[i] != 0) {
      answer += dp[i][nums] + (d[i] - 1) * dp[i][--nums];
    }
  }
  return answer;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cachefact(31);
  for (int i = 0; i <= 30; i++) {
    dp[i][0] = 1;
    dp[i][1] = 1 + i * 9;
    dp[i][2] = 1 + i * 9 + C(i, 2) * 81;
    dp[i][3] = 1 + i * 9 + C(i, 2) * 81 + C(i, 3) * 729;
  }
  int t;
  cin >> t;
  while (t--) {
    ll L, R;
    cin >> L >> R;
    cout << F(R) - F(L - 1) << "\n";
  }
  return 0;
}

```