#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename T0>
void read(T &x, T0 &y) {
  cin >> x >> y;
}
template <typename T, typename T0, typename T1>
void read(T &x, T0 &y, T1 &z) {
  cin >> x >> y >> z;
}
template <typename T, typename T0, typename T1, typename T2>
void read(T &x, T0 &y, T1 &z, T2 &w) {
  cin >> x >> y >> z >> w;
}
template <typename T, typename T0>
void read(pair<T, T0> &p) {
  cin >> p.first >> p.second;
}
template <typename T>
void read(vector<T> &oneD, long long int n) {
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int x;
    read(x);
    oneD.push_back(x);
  }
}
template <typename T>
void read(T oneD[], long long int n) {
  for (long long int i = 0; i < n; i++) {
    read(oneD[i]);
  }
}
template <typename T>
void write(T &x) {
  cout << x << " ";
}
template <typename T, typename T0>
void write(T &x, T0 &y) {
  cout << x << " " << y << "\n";
}
template <typename T, typename T0, typename T1>
void write(T &x, T0 &y, T1 &z) {
  cout << x << " " << y << " " << z << "\n";
}
template <typename T, typename T0, typename T1, typename T2>
void write(T &x, T0 &y, T1 &z, T2 &w) {
  cout << x << " " << y << " " << z << " " << w << "\n";
}
template <typename T, typename T0>
void write(pair<T, T0> &p) {
  write(p.first);
  write(p.second);
  cout << endl;
}
template <typename T>
void write(vector<T> &oneD, long long int n) {
  for (long long int i = 0; i < n; i++) {
    cout << oneD[i] << " ";
  }
  cout << endl;
}
template <typename T>
void write(T oneD[], int n) {
  for (long long int i = 0; i < n; i++) {
    write(oneD[i]);
  }
  cout << endl;
}
template <typename T, typename T0>
void write(map<T, T0> &mpp) {
  for (auto it : mpp) {
    write(it.first);
    cout << ": ";
    write(it.second);
    cout << "\n";
  }
  cout << endl;
}
vector<long long int> seive;
void Seive() {
  const long long int maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long int(i) = 0; (i) < (maxn); ++(i)) seive[i] = i;
  for (long long int(i) = 2; (i) <= (maxn); (i) += (2)) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long int i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long int j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
long long int extended_GCD(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int find_x_CRT(long long int num[], long long int rem[],
                         long long int n) {
  long long int pro = 1;
  for (long long int(i) = 0; (i) < (n); ++(i)) pro *= num[i];
  long long int res = 0;
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int pp = pro / num[i];
    res += (rem[i] * modinv(pp, num[i]) * pp);
  }
  res %= pro;
  return res;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int powe(long long int a, long long int b,
                   long long int m = 1000000007) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
string getString(char x) {
  string s(1, x);
  return s;
}
void update(vector<long long int> &BIT, long long int index,
            long long int inc) {
  while (index <= (long long int)(BIT.size())) {
    BIT[index] += inc;
    index += (index & (-index));
  }
}
long long int query(vector<long long int> &BIT, long long int index) {
  long long int sum = 0;
  while (index > 0) {
    sum += BIT[index];
    index -= (index & (-index));
  }
  return sum;
}
void make_set(long long int v, vector<long long int> &parent,
              vector<long long int> &siz) {
  parent[v] = v;
  siz[v] = 1;
}
long long int find_set(long long int x, vector<long long int> &parent) {
  if (x == parent[x])
    return x;
  else {
    return parent[x] = find_set(parent[x], parent);
  }
}
void union_set(long long int a, long long int b, vector<long long int> &siz,
               vector<long long int> &parent) {
  a = find_set(a, parent);
  b = find_set(b, parent);
  if (a != b) {
    if (siz[a] < siz[b]) swap(a, b);
    parent[b] = a;
    siz[a] += siz[b];
    siz[b] = 0;
  }
}
void precompute_NCR(vector<long long int> &fact) {
  const long long int N = 1e6 + 5;
  fact[0] = 1;
  for (long long int(i) = 1; (i) <= ((N - 1)); (i) += (1)) {
    long long int y = (i % 1000000007 * fact[i - 1] % 1000000007) % 1000000007;
    fact[i] = y;
  }
}
long long int NCR(vector<long long int> &fact, long long int N, long long int R,
                  long long int mod = 1000000007) {
  long long int n = fact[N];
  long long int r = fact[R];
  long long int n_r = fact[N - R];
  long long int y = (r % mod * n_r % mod) % mod;
  long long int z = modinv(y, mod);
  long long int ans = (n % mod * z % mod) % mod;
  return ans;
}
void shuru_karte_hai_bina_kise_bakchodi_ke() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
}
string tostring(long long int x) {
  if (x == 0) return "0";
  string ans = "";
  while (x > 0) {
    long long int d = x % 10;
    char y = d + '0';
    ans += getString(y);
    x /= 10;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
string s;
long long int dp[20][5][2] = {};
long long int solve(long long int pos, long long int cnt, long long int tight,
                    long long int en) {
  if (pos == en) return 1;
  if (dp[pos][cnt][tight] != -1) return dp[pos][cnt][tight];
  long long int end = tight ? (s[pos] - '0') : 9;
  long long int ans = 0;
  for (long long int i = 0; i <= end; i++) {
    long long int cntup = cnt + (i > 0);
    if (cntup <= 3) {
      ans += solve((pos + 1), cntup, tight & (i == end), en);
    }
  }
  dp[pos][cnt][tight] = ans;
  return ans;
}
int main() {
  shuru_karte_hai_bina_kise_bakchodi_ke();
  long long int t;
  read(t);
  while (t--) {
    long long int l, r;
    read(l, r);
    s = to_string(r);
    memset(dp, -1, sizeof(dp));
    long long int ans1 = solve(0, 0, 1, s.length());
    l -= 1;
    s = to_string(l);
    memset(dp, -1, sizeof(dp));
    long long int ans2 = solve(0, 0, 1, s.length());
    cout << (ans1 - ans2) << "\n";
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution 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>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename T0>
void read(T &x, T0 &y) {
  cin >> x >> y;
}
template <typename T, typename T0, typename T1>
void read(T &x, T0 &y, T1 &z) {
  cin >> x >> y >> z;
}
template <typename T, typename T0, typename T1, typename T2>
void read(T &x, T0 &y, T1 &z, T2 &w) {
  cin >> x >> y >> z >> w;
}
template <typename T, typename T0>
void read(pair<T, T0> &p) {
  cin >> p.first >> p.second;
}
template <typename T>
void read(vector<T> &oneD, long long int n) {
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int x;
    read(x);
    oneD.push_back(x);
  }
}
template <typename T>
void read(T oneD[], long long int n) {
  for (long long int i = 0; i < n; i++) {
    read(oneD[i]);
  }
}
template <typename T>
void write(T &x) {
  cout << x << " ";
}
template <typename T, typename T0>
void write(T &x, T0 &y) {
  cout << x << " " << y << "\n";
}
template <typename T, typename T0, typename T1>
void write(T &x, T0 &y, T1 &z) {
  cout << x << " " << y << " " << z << "\n";
}
template <typename T, typename T0, typename T1, typename T2>
void write(T &x, T0 &y, T1 &z, T2 &w) {
  cout << x << " " << y << " " << z << " " << w << "\n";
}
template <typename T, typename T0>
void write(pair<T, T0> &p) {
  write(p.first);
  write(p.second);
  cout << endl;
}
template <typename T>
void write(vector<T> &oneD, long long int n) {
  for (long long int i = 0; i < n; i++) {
    cout << oneD[i] << " ";
  }
  cout << endl;
}
template <typename T>
void write(T oneD[], int n) {
  for (long long int i = 0; i < n; i++) {
    write(oneD[i]);
  }
  cout << endl;
}
template <typename T, typename T0>
void write(map<T, T0> &mpp) {
  for (auto it : mpp) {
    write(it.first);
    cout << ": ";
    write(it.second);
    cout << "\n";
  }
  cout << endl;
}
vector<long long int> seive;
void Seive() {
  const long long int maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long int(i) = 0; (i) < (maxn); ++(i)) seive[i] = i;
  for (long long int(i) = 2; (i) <= (maxn); (i) += (2)) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long int i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long int j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
long long int extended_GCD(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int find_x_CRT(long long int num[], long long int rem[],
                         long long int n) {
  long long int pro = 1;
  for (long long int(i) = 0; (i) < (n); ++(i)) pro *= num[i];
  long long int res = 0;
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int pp = pro / num[i];
    res += (rem[i] * modinv(pp, num[i]) * pp);
  }
  res %= pro;
  return res;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int powe(long long int a, long long int b,
                   long long int m = 1000000007) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
string getString(char x) {
  string s(1, x);
  return s;
}
void update(vector<long long int> &BIT, long long int index,
            long long int inc) {
  while (index <= (long long int)(BIT.size())) {
    BIT[index] += inc;
    index += (index & (-index));
  }
}
long long int query(vector<long long int> &BIT, long long int index) {
  long long int sum = 0;
  while (index > 0) {
    sum += BIT[index];
    index -= (index & (-index));
  }
  return sum;
}
void make_set(long long int v, vector<long long int> &parent,
              vector<long long int> &siz) {
  parent[v] = v;
  siz[v] = 1;
}
long long int find_set(long long int x, vector<long long int> &parent) {
  if (x == parent[x])
    return x;
  else {
    return parent[x] = find_set(parent[x], parent);
  }
}
void union_set(long long int a, long long int b, vector<long long int> &siz,
               vector<long long int> &parent) {
  a = find_set(a, parent);
  b = find_set(b, parent);
  if (a != b) {
    if (siz[a] < siz[b]) swap(a, b);
    parent[b] = a;
    siz[a] += siz[b];
    siz[b] = 0;
  }
}
void precompute_NCR(vector<long long int> &fact) {
  const long long int N = 1e6 + 5;
  fact[0] = 1;
  for (long long int(i) = 1; (i) <= ((N - 1)); (i) += (1)) {
    long long int y = (i % 1000000007 * fact[i - 1] % 1000000007) % 1000000007;
    fact[i] = y;
  }
}
long long int NCR(vector<long long int> &fact, long long int N, long long int R,
                  long long int mod = 1000000007) {
  long long int n = fact[N];
  long long int r = fact[R];
  long long int n_r = fact[N - R];
  long long int y = (r % mod * n_r % mod) % mod;
  long long int z = modinv(y, mod);
  long long int ans = (n % mod * z % mod) % mod;
  return ans;
}
void shuru_karte_hai_bina_kise_bakchodi_ke() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
}
string tostring(long long int x) {
  if (x == 0) return "0";
  string ans = "";
  while (x > 0) {
    long long int d = x % 10;
    char y = d + '0';
    ans += getString(y);
    x /= 10;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}
string s;
long long int dp[20][5][2] = {};
long long int solve(long long int pos, long long int cnt, long long int tight,
                    long long int en) {
  if (pos == en) return 1;
  if (dp[pos][cnt][tight] != -1) return dp[pos][cnt][tight];
  long long int end = tight ? (s[pos] - '0') : 9;
  long long int ans = 0;
  for (long long int i = 0; i <= end; i++) {
    long long int cntup = cnt + (i > 0);
    if (cntup <= 3) {
      ans += solve((pos + 1), cntup, tight & (i == end), en);
    }
  }
  dp[pos][cnt][tight] = ans;
  return ans;
}
int main() {
  shuru_karte_hai_bina_kise_bakchodi_ke();
  long long int t;
  read(t);
  while (t--) {
    long long int l, r;
    read(l, r);
    s = to_string(r);
    memset(dp, -1, sizeof(dp));
    long long int ans1 = solve(0, 0, 1, s.length());
    l -= 1;
    s = to_string(l);
    memset(dp, -1, sizeof(dp));
    long long int ans2 = solve(0, 0, 1, s.length());
    cout << (ans1 - ans2) << "\n";
  }
  return 0;
}

```