#include <bits/stdc++.h>
using namespace std;
ofstream fo("test.out");
ifstream fi("test.inp");
const long long MOD = 1e9 + 7;
const long long base = 269;
const int oo = 1 << 30;
const int N = 1e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long P(long long x, long long y) {
  long long ret = 1;
  while (y > 0) {
    if (y & 1) ret *= x;
    y /= 2;
    x = x * x;
  }
  return ret;
}
long long GCD(long long a, long long b) { return (b ? GCD(b, a % b) : a); }
int gi() {
  int w = 0;
  bool q = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 0, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? w : -w;
}
namespace io {
const int L = (1 << 21) + 1;
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55];
int f, tp;
inline char getc() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <class I>
inline bool gi(I& x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == -1)
      return false;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return true;
}
template <class I>
inline void print(I x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) st[++tp] = x % 10 + '0', x /= 10;
  while (tp) putc(st[tp--]);
}
inline bool gs(char* s, int& l) {
  for (c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c < 'a' || c > 'z';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == -1) return false;
  for (l = 0; c <= 'z' && c >= 'a';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    s[l++] = c;
  s[l] = 0;
  return true;
}
inline void printld(double x, int digit) {
  if (x < 0) putc('-'), x = -x;
  x += 0.5 * pow(0.1, digit);
  print((long long)x), putc('.');
  for (x -= (long long)x; digit; --digit)
    x = x * 10, putc((int)x + '0'), x -= (int)x;
}
inline void ps(const char* s) {
  for (int i = 0, n = strlen(s); i < n; i++) putc(s[i]);
}
struct IOFLUSHER {
  ~IOFLUSHER() { flush(); }
} _ioflusher_;
};  // namespace io
using io::getc;
using io::gi;
using io::gs;
using io::print;
using io::printld;
using io::ps;
using io::putc;
void inp_outp() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
long long n, m, q, k, pos, rs, check;
vector<unsigned long long> ans;
void dfs(unsigned long long num, unsigned long long cnt,
         unsigned long long cur) {
  if (num == 18) {
    ans.push_back(cur);
    return;
  }
  dfs(num + 1, cnt, cur * 10);
  if (cnt < 3) {
    for (long long(i) = 1; (i) <= (9); (i)++)
      dfs(num + 1, cnt + 1, cur * 10 + i);
  }
}
long long BS_Upper(long long x) {
  long long l = 0, r = ans.size() - 1, mid, ret;
  while (l <= r) {
    mid = (l + r) / 2;
    if (ans[mid] < x)
      l = mid + 1;
    else {
      ret = mid;
      r = mid - 1;
    }
  }
  return ret;
}
long long BS_Lower(long long x) {
  long long l = 0, r = ans.size() - 1, mid, ret;
  while (l <= r) {
    mid = (l + r) / 2;
    if (ans[mid] > x)
      r = mid - 1;
    else {
      ret = mid;
      l = mid + 1;
    }
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  dfs(0, 0, 0);
  ans.push_back(1e18);
  cin >> q;
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << BS_Lower(r) - BS_Upper(l) + 1 << "\n";
  }
}

### Prompt

Please create a solution in Cpp to 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;
ofstream fo("test.out");
ifstream fi("test.inp");
const long long MOD = 1e9 + 7;
const long long base = 269;
const int oo = 1 << 30;
const int N = 1e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long P(long long x, long long y) {
  long long ret = 1;
  while (y > 0) {
    if (y & 1) ret *= x;
    y /= 2;
    x = x * x;
  }
  return ret;
}
long long GCD(long long a, long long b) { return (b ? GCD(b, a % b) : a); }
int gi() {
  int w = 0;
  bool q = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') q = 0, c = getchar();
  while (c >= '0' && c <= '9') w = w * 10 + c - '0', c = getchar();
  return q ? w : -w;
}
namespace io {
const int L = (1 << 21) + 1;
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55];
int f, tp;
inline char getc() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <class I>
inline bool gi(I& x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == -1)
      return false;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return true;
}
template <class I>
inline void print(I x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) st[++tp] = x % 10 + '0', x /= 10;
  while (tp) putc(st[tp--]);
}
inline bool gs(char* s, int& l) {
  for (c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c < 'a' || c > 'z';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == -1) return false;
  for (l = 0; c <= 'z' && c >= 'a';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    s[l++] = c;
  s[l] = 0;
  return true;
}
inline void printld(double x, int digit) {
  if (x < 0) putc('-'), x = -x;
  x += 0.5 * pow(0.1, digit);
  print((long long)x), putc('.');
  for (x -= (long long)x; digit; --digit)
    x = x * 10, putc((int)x + '0'), x -= (int)x;
}
inline void ps(const char* s) {
  for (int i = 0, n = strlen(s); i < n; i++) putc(s[i]);
}
struct IOFLUSHER {
  ~IOFLUSHER() { flush(); }
} _ioflusher_;
};  // namespace io
using io::getc;
using io::gi;
using io::gs;
using io::print;
using io::printld;
using io::ps;
using io::putc;
void inp_outp() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
long long n, m, q, k, pos, rs, check;
vector<unsigned long long> ans;
void dfs(unsigned long long num, unsigned long long cnt,
         unsigned long long cur) {
  if (num == 18) {
    ans.push_back(cur);
    return;
  }
  dfs(num + 1, cnt, cur * 10);
  if (cnt < 3) {
    for (long long(i) = 1; (i) <= (9); (i)++)
      dfs(num + 1, cnt + 1, cur * 10 + i);
  }
}
long long BS_Upper(long long x) {
  long long l = 0, r = ans.size() - 1, mid, ret;
  while (l <= r) {
    mid = (l + r) / 2;
    if (ans[mid] < x)
      l = mid + 1;
    else {
      ret = mid;
      r = mid - 1;
    }
  }
  return ret;
}
long long BS_Lower(long long x) {
  long long l = 0, r = ans.size() - 1, mid, ret;
  while (l <= r) {
    mid = (l + r) / 2;
    if (ans[mid] > x)
      r = mid - 1;
    else {
      ret = mid;
      l = mid + 1;
    }
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  dfs(0, 0, 0);
  ans.push_back(1e18);
  cin >> q;
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << BS_Lower(r) - BS_Upper(l) + 1 << "\n";
  }
}

```