#include <bits/stdc++.h>
using namespace std;
long long dp[25][5][25];
long long f(long long p, long long tk, long long len) {
  if (tk < 0) return 0;
  if (p == 0) return 1;
  if (dp[p][tk][len] == -1) {
    long long tmp = 0;
    if (p == len)
      tmp = 9 * f(p - 1, tk - 1, len);
    else
      tmp = 9 * f(p - 1, tk - 1, len) + f(p - 1, tk, len);
    dp[p][tk][len] = tmp;
  }
  return dp[p][tk][len];
}
string s;
long long n;
long long d[25][5][4];
long long dig(char c) { return c - '0'; }
long long ff(long long p, long long tk, bool ch) {
  if (tk < 0) return 0;
  if (p == n) return 1;
  if (d[p][tk][ch] == -1) {
    long long tmp = 0;
    if (p == 0) {
      tmp = (dig(s[p]) - 1) * ff(p + 1, tk - 1, 0) + ff(p + 1, tk - 1, 1);
    } else if (ch == 0) {
      tmp = 9 * ff(p + 1, tk - 1, 0) + ff(p + 1, tk, 0);
    } else {
      if (s[p] == '0') {
        tmp = ff(p + 1, tk, 1);
      } else {
        tmp = (dig(s[p]) - 1) * ff(p + 1, tk - 1, 0) + ff(p + 1, tk - 1, 1) +
              ff(p + 1, tk, 0);
      }
    }
    d[p][tk][ch] = tmp;
  }
  return d[p][tk][ch];
}
long long get() {
  memset(d, -1, sizeof d);
  n = s.length();
  long long sum = 0;
  for (long long i = 1; i <= n - 1; i++) {
    sum += f(i, 3, i);
  }
  sum += ff(0, 3, 0);
  return sum;
}
bool ch() {
  long long r = 0;
  for (long long i = 0; i < n; i++)
    if (dig(s[i]) != 0) r++;
  return r <= 3;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long tc;
  memset(dp, -1, sizeof dp);
  cin >> tc;
  while (tc--) {
    cin >> s;
    n = s.length();
    long long ex = ch();
    long long v1 = get();
    cin >> s;
    n = s.length();
    long long v2 = get();
    cout << v2 - v1 + ex << '\n';
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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;
long long dp[25][5][25];
long long f(long long p, long long tk, long long len) {
  if (tk < 0) return 0;
  if (p == 0) return 1;
  if (dp[p][tk][len] == -1) {
    long long tmp = 0;
    if (p == len)
      tmp = 9 * f(p - 1, tk - 1, len);
    else
      tmp = 9 * f(p - 1, tk - 1, len) + f(p - 1, tk, len);
    dp[p][tk][len] = tmp;
  }
  return dp[p][tk][len];
}
string s;
long long n;
long long d[25][5][4];
long long dig(char c) { return c - '0'; }
long long ff(long long p, long long tk, bool ch) {
  if (tk < 0) return 0;
  if (p == n) return 1;
  if (d[p][tk][ch] == -1) {
    long long tmp = 0;
    if (p == 0) {
      tmp = (dig(s[p]) - 1) * ff(p + 1, tk - 1, 0) + ff(p + 1, tk - 1, 1);
    } else if (ch == 0) {
      tmp = 9 * ff(p + 1, tk - 1, 0) + ff(p + 1, tk, 0);
    } else {
      if (s[p] == '0') {
        tmp = ff(p + 1, tk, 1);
      } else {
        tmp = (dig(s[p]) - 1) * ff(p + 1, tk - 1, 0) + ff(p + 1, tk - 1, 1) +
              ff(p + 1, tk, 0);
      }
    }
    d[p][tk][ch] = tmp;
  }
  return d[p][tk][ch];
}
long long get() {
  memset(d, -1, sizeof d);
  n = s.length();
  long long sum = 0;
  for (long long i = 1; i <= n - 1; i++) {
    sum += f(i, 3, i);
  }
  sum += ff(0, 3, 0);
  return sum;
}
bool ch() {
  long long r = 0;
  for (long long i = 0; i < n; i++)
    if (dig(s[i]) != 0) r++;
  return r <= 3;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long tc;
  memset(dp, -1, sizeof dp);
  cin >> tc;
  while (tc--) {
    cin >> s;
    n = s.length();
    long long ex = ch();
    long long v1 = get();
    cin >> s;
    n = s.length();
    long long v2 = get();
    cout << v2 - v1 + ex << '\n';
  }
  return 0;
}

```