#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9 + 9;
const long long inf = 1e18 + 18;
const int max6 = 1e6 + 6;
const int modx = 1e9 + 123;
const int mody = 997;
const int base = 137;
long long Pow(int a, int b) {
  if (b == 0) return 1;
  long long half = Pow(a, b / 2);
  long long res = half * half;
  if (b % 2) res = res * a;
  return res;
}
long long C(int k, int n) {
  if (k > n) return 0;
  long long res = 1;
  for (int i = k + 1; i <= n; ++i) res *= i;
  for (int i = 1; i <= n - k; ++i) res /= i;
  return res;
}
vector<int> d;
int siz;
long long cal(int id, int on_boundary, int remain) {
  if (remain < 0) return 0;
  if (id == siz + 1) {
    return remain == 0;
  }
  long long res = 0;
  if (on_boundary) {
    for (int i = 0; i <= d[id - 1]; ++i)
      res += cal(id + 1, i == d[id - 1], remain - (i > 0));
    return res;
  }
  res = Pow(9, remain) * C(remain, siz - id + 1);
  return res;
}
long long sol(long long first) {
  if (first == 0) return 0;
  d.clear();
  while (first) {
    int id = first % 10;
    first /= 10;
    d.push_back(id);
  }
  reverse(d.begin(), d.end());
  siz = d.size();
  long long res = 0;
  for (int len = 1; len < siz; ++len)
    for (int j = 1; j <= 3 && j <= len; ++j)
      res += Pow(9, j) * C(j - 1, len - 1);
  for (int i = 1; i <= d[0]; ++i)
    for (int j = 1; j <= 3; ++j) res += cal(2, i == d[0], j - (i > 0));
  return res;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long l, r;
    cin >> l >> r;
    cout << sol(r) - sol(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;
const int oo = 1e9 + 9;
const long long inf = 1e18 + 18;
const int max6 = 1e6 + 6;
const int modx = 1e9 + 123;
const int mody = 997;
const int base = 137;
long long Pow(int a, int b) {
  if (b == 0) return 1;
  long long half = Pow(a, b / 2);
  long long res = half * half;
  if (b % 2) res = res * a;
  return res;
}
long long C(int k, int n) {
  if (k > n) return 0;
  long long res = 1;
  for (int i = k + 1; i <= n; ++i) res *= i;
  for (int i = 1; i <= n - k; ++i) res /= i;
  return res;
}
vector<int> d;
int siz;
long long cal(int id, int on_boundary, int remain) {
  if (remain < 0) return 0;
  if (id == siz + 1) {
    return remain == 0;
  }
  long long res = 0;
  if (on_boundary) {
    for (int i = 0; i <= d[id - 1]; ++i)
      res += cal(id + 1, i == d[id - 1], remain - (i > 0));
    return res;
  }
  res = Pow(9, remain) * C(remain, siz - id + 1);
  return res;
}
long long sol(long long first) {
  if (first == 0) return 0;
  d.clear();
  while (first) {
    int id = first % 10;
    first /= 10;
    d.push_back(id);
  }
  reverse(d.begin(), d.end());
  siz = d.size();
  long long res = 0;
  for (int len = 1; len < siz; ++len)
    for (int j = 1; j <= 3 && j <= len; ++j)
      res += Pow(9, j) * C(j - 1, len - 1);
  for (int i = 1; i <= d[0]; ++i)
    for (int j = 1; j <= 3; ++j) res += cal(2, i == d[0], j - (i > 0));
  return res;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long l, r;
    cin >> l >> r;
    cout << sol(r) - sol(l - 1) << "\n";
  }
}

```