#include <bits/stdc++.h>
using namespace std;
int t;
bool used[20][4], luogu;
long long l, r, f[20][4], a[20];
long long dfs(int poi, int lft, bool top, bool lmt) {
  if (poi == 0) {
    return 1;
  }
  if (!lmt && !top && used[poi][lft]) {
    return f[poi][lft];
  }
  long long rep = 0;
  int lim = lmt ? a[poi] : 9;
  rep += dfs(poi - 1, lft, top, lmt && a[poi] == 0);
  if (lft) {
    for (int i = 1; i <= lim; i++) {
      rep += dfs(poi - 1, lft - 1, false, lmt && i == a[poi]);
    }
  }
  if (!lmt && !top) {
    f[poi][lft] = rep;
    used[poi][lft] = true;
  }
  return rep;
}
long long solve(long long u) {
  if (u == 0) {
    return 1;
  }
  int cnt = 0;
  memset(used, false, sizeof used);
  memset(f, 0, sizeof f);
  while (u) {
    a[++cnt] = u % 10;
    u /= 10;
  }
  return dfs(cnt, 3, true, true);
}
int main() {
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    scanf("%lld%lld", &l, &r);
    printf("%lld\n", solve(r) - solve(l - 1));
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
int t;
bool used[20][4], luogu;
long long l, r, f[20][4], a[20];
long long dfs(int poi, int lft, bool top, bool lmt) {
  if (poi == 0) {
    return 1;
  }
  if (!lmt && !top && used[poi][lft]) {
    return f[poi][lft];
  }
  long long rep = 0;
  int lim = lmt ? a[poi] : 9;
  rep += dfs(poi - 1, lft, top, lmt && a[poi] == 0);
  if (lft) {
    for (int i = 1; i <= lim; i++) {
      rep += dfs(poi - 1, lft - 1, false, lmt && i == a[poi]);
    }
  }
  if (!lmt && !top) {
    f[poi][lft] = rep;
    used[poi][lft] = true;
  }
  return rep;
}
long long solve(long long u) {
  if (u == 0) {
    return 1;
  }
  int cnt = 0;
  memset(used, false, sizeof used);
  memset(f, 0, sizeof f);
  while (u) {
    a[++cnt] = u % 10;
    u /= 10;
  }
  return dfs(cnt, 3, true, true);
}
int main() {
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    scanf("%lld%lld", &l, &r);
    printf("%lld\n", solve(r) - solve(l - 1));
  }
  return 0;
}

```