#include <bits/stdc++.h>
using namespace std;
void arraychk(int a[], int n) {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << "\n";
  ;
}
long long int dp[20][4][2], arr[2][20];
long long int call(bool konta, long long int crnt, long long int done,
                   long long int prevfixed) {
  if (done == 3) return dp[crnt][done][0] = dp[crnt][done][1] = 1;
  if (crnt == 0) {
    long long int tmp;
    if (prevfixed)
      tmp = arr[konta][0] + 1;
    else
      tmp = 10;
    dp[crnt][done][prevfixed] = tmp;
    return tmp;
  }
  if (dp[crnt][done][prevfixed] != -1) return dp[crnt][done][prevfixed];
  if (prevfixed) {
    if (arr[konta][crnt] == 0) {
      dp[crnt][done][1] = call(konta, crnt - 1, done, 1);
    } else {
      dp[crnt][done][1] = call(konta, crnt - 1, done, 0);
      for (int i = 1; i < arr[konta][crnt]; i++)
        dp[crnt][done][1] += call(konta, crnt - 1, done + 1, 0);
      dp[crnt][done][1] += call(konta, crnt - 1, done + 1, 1);
    }
  } else {
    dp[crnt][done][0] = call(konta, crnt - 1, done, 0);
    dp[crnt][done][0] += call(konta, crnt - 1, done + 1, 0) * 9;
  }
  return dp[crnt][done][prevfixed];
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long int tt = 1;
  cin >> tt;
  for (int cse = 1; cse <= tt; cse++) {
    long long int n, m, x = 0, y = 0, tn, tm, ans;
    ;
    cin >> tn >> tm;
    n = tn, m = tm;
    while (n) {
      arr[1][x++] = n % 10;
      n /= 10;
    }
    while (m) {
      arr[0][y++] = m % 10;
      m /= 10;
    }
    n = tn, m = tm;
    memset((dp), (-1), sizeof(dp));
    call(1, x - 1, 0, 1);
    tn = max(0ll, dp[x - 1][0][0]) + max(0ll, dp[x - 1][1][1]);
    tn += max(0ll, dp[x - 1][1][0]) + max(0ll, dp[x - 1][0][1]);
    memset((dp), (-1), sizeof(dp));
    call(0, y - 1, 0, 1);
    tm = max(0ll, dp[y - 1][0][0]) + max(0ll, dp[y - 1][1][1]);
    tm += max(0ll, dp[y - 1][1][0]) + max(0ll, dp[y - 1][0][1]);
    ans = tm - tn;
    tn = n;
    x = 0;
    y = 0;
    while (tn) {
      if (tn % 10) x++;
      tn /= 10;
    }
    if (x <= 3) ans++;
    cout << ans << endl;
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
void arraychk(int a[], int n) {
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  cout << "\n";
  ;
}
long long int dp[20][4][2], arr[2][20];
long long int call(bool konta, long long int crnt, long long int done,
                   long long int prevfixed) {
  if (done == 3) return dp[crnt][done][0] = dp[crnt][done][1] = 1;
  if (crnt == 0) {
    long long int tmp;
    if (prevfixed)
      tmp = arr[konta][0] + 1;
    else
      tmp = 10;
    dp[crnt][done][prevfixed] = tmp;
    return tmp;
  }
  if (dp[crnt][done][prevfixed] != -1) return dp[crnt][done][prevfixed];
  if (prevfixed) {
    if (arr[konta][crnt] == 0) {
      dp[crnt][done][1] = call(konta, crnt - 1, done, 1);
    } else {
      dp[crnt][done][1] = call(konta, crnt - 1, done, 0);
      for (int i = 1; i < arr[konta][crnt]; i++)
        dp[crnt][done][1] += call(konta, crnt - 1, done + 1, 0);
      dp[crnt][done][1] += call(konta, crnt - 1, done + 1, 1);
    }
  } else {
    dp[crnt][done][0] = call(konta, crnt - 1, done, 0);
    dp[crnt][done][0] += call(konta, crnt - 1, done + 1, 0) * 9;
  }
  return dp[crnt][done][prevfixed];
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long int tt = 1;
  cin >> tt;
  for (int cse = 1; cse <= tt; cse++) {
    long long int n, m, x = 0, y = 0, tn, tm, ans;
    ;
    cin >> tn >> tm;
    n = tn, m = tm;
    while (n) {
      arr[1][x++] = n % 10;
      n /= 10;
    }
    while (m) {
      arr[0][y++] = m % 10;
      m /= 10;
    }
    n = tn, m = tm;
    memset((dp), (-1), sizeof(dp));
    call(1, x - 1, 0, 1);
    tn = max(0ll, dp[x - 1][0][0]) + max(0ll, dp[x - 1][1][1]);
    tn += max(0ll, dp[x - 1][1][0]) + max(0ll, dp[x - 1][0][1]);
    memset((dp), (-1), sizeof(dp));
    call(0, y - 1, 0, 1);
    tm = max(0ll, dp[y - 1][0][0]) + max(0ll, dp[y - 1][1][1]);
    tm += max(0ll, dp[y - 1][1][0]) + max(0ll, dp[y - 1][0][1]);
    ans = tm - tn;
    tn = n;
    x = 0;
    y = 0;
    while (tn) {
      if (tn % 10) x++;
      tn /= 10;
    }
    if (x <= 3) ans++;
    cout << ans << endl;
  }
  return 0;
}

```