#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF64 = 1e18;
const long long INF32 = 1e9;
const double EPS = static_cast<double>(1e-10);
const double PI = 2.0 * acos(0.0);
const long long MOD = (long long)1e9 + 7;
long long powMod(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
long long invMod(long long a) {
  long long b = MOD, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  return (MOD + u) % MOD;
}
const long long day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
mt19937 rnd(239);
vector<long long> prefixSum(vector<long long> &a) {
  vector<long long> b;
  std::partial_sum(a.begin(), a.end(), b.begin());
  return b;
}
long long mostSignDigit(long long n) {
  double k = log10(n);
  return (long long)pow(10, k - floor(k));
}
long long numOfDigits(long long n) { return (long long)floor(log10(n)) + 1; }
bool isPowerOfTwo(long long x) { return x && (!(x & (x - 1))); }
bool allPositive(vector<long long> &a) {
  return all_of(begin(a), end(a), [](long long x) { return x > 0; });
}
bool anyPositive(vector<long long> &a) {
  return any_of(begin(a), end(a), [](long long x) { return x > 0; });
}
bool nonePositive(vector<long long> &a) {
  return none_of(begin(a), end(a), [](long long x) { return x > 0; });
}
void FILEIO() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
}
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "T" : "F"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long f(long long r) {
  vector<long long> vr;
  while (r) {
    vr.push_back(r % 10);
    r /= 10;
  }
  reverse(begin(vr), end(vr));
  long long n = ((long long)(vr).size());
  ;
  vector<vector<long long>> dp0(20, vector<long long>(4, 0)),
      dp1(20, vector<long long>(4, 0));
  for (long long i = (0); i < (n); i++) {
    dp0[i][0] = dp1[i][0] = 1;
  }
  dp0[n - 1][1] = 9;
  dp0[n - 1][2] = 0;
  dp0[n - 1][3] = 0;
  dp1[n - 1][1] = vr[n - 1], dp1[n - 1][2] = dp1[n - 1][3] = 0;
  ;
  ;
  for (long long i = (n - 2); i >= (0); i--) {
    for (long long j = (1); j <= (3); j++)
      dp0[i][j] = dp0[i + 1][j] + 9 * dp0[i + 1][j - 1];
    for (long long j = (1); j <= (3); j++) {
      if (vr[i] == 0)
        dp1[i][j] = dp1[i + 1][j];
      else {
        dp1[i][j] = dp1[i + 1][j - 1];
        dp1[i][j] += (vr[i] - 1) * dp0[i + 1][j - 1];
        dp1[i][j] += dp0[i + 1][j];
      }
    }
  };
  ;
  return dp1[0][3] + dp1[0][2] + dp1[0][1];
}
void solve() {
  long long l, r;
  cin >> l >> r;
  if (l == 1)
    cout << f(r) << endl;
  else
    cout << f(r) - f(l - 1) << endl;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  long long tc;
  cin >> tc;
  for (long long i = (1); i <= (tc); i++) {
    solve();
  }
  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>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF64 = 1e18;
const long long INF32 = 1e9;
const double EPS = static_cast<double>(1e-10);
const double PI = 2.0 * acos(0.0);
const long long MOD = (long long)1e9 + 7;
long long powMod(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
long long invMod(long long a) {
  long long b = MOD, u = 1, v = 0;
  while (b) {
    long long t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  return (MOD + u) % MOD;
}
const long long day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
mt19937 rnd(239);
vector<long long> prefixSum(vector<long long> &a) {
  vector<long long> b;
  std::partial_sum(a.begin(), a.end(), b.begin());
  return b;
}
long long mostSignDigit(long long n) {
  double k = log10(n);
  return (long long)pow(10, k - floor(k));
}
long long numOfDigits(long long n) { return (long long)floor(log10(n)) + 1; }
bool isPowerOfTwo(long long x) { return x && (!(x & (x - 1))); }
bool allPositive(vector<long long> &a) {
  return all_of(begin(a), end(a), [](long long x) { return x > 0; });
}
bool anyPositive(vector<long long> &a) {
  return any_of(begin(a), end(a), [](long long x) { return x > 0; });
}
bool nonePositive(vector<long long> &a) {
  return none_of(begin(a), end(a), [](long long x) { return x > 0; });
}
void FILEIO() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
}
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "T" : "F"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long f(long long r) {
  vector<long long> vr;
  while (r) {
    vr.push_back(r % 10);
    r /= 10;
  }
  reverse(begin(vr), end(vr));
  long long n = ((long long)(vr).size());
  ;
  vector<vector<long long>> dp0(20, vector<long long>(4, 0)),
      dp1(20, vector<long long>(4, 0));
  for (long long i = (0); i < (n); i++) {
    dp0[i][0] = dp1[i][0] = 1;
  }
  dp0[n - 1][1] = 9;
  dp0[n - 1][2] = 0;
  dp0[n - 1][3] = 0;
  dp1[n - 1][1] = vr[n - 1], dp1[n - 1][2] = dp1[n - 1][3] = 0;
  ;
  ;
  for (long long i = (n - 2); i >= (0); i--) {
    for (long long j = (1); j <= (3); j++)
      dp0[i][j] = dp0[i + 1][j] + 9 * dp0[i + 1][j - 1];
    for (long long j = (1); j <= (3); j++) {
      if (vr[i] == 0)
        dp1[i][j] = dp1[i + 1][j];
      else {
        dp1[i][j] = dp1[i + 1][j - 1];
        dp1[i][j] += (vr[i] - 1) * dp0[i + 1][j - 1];
        dp1[i][j] += dp0[i + 1][j];
      }
    }
  };
  ;
  return dp1[0][3] + dp1[0][2] + dp1[0][1];
}
void solve() {
  long long l, r;
  cin >> l >> r;
  if (l == 1)
    cout << f(r) << endl;
  else
    cout << f(r) - f(l - 1) << endl;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  long long tc;
  cin >> tc;
  for (long long i = (1); i <= (tc); i++) {
    solve();
  }
  return 0;
}

```