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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int st[7], dim;
long long ans[5000005];
inline void Build3() {
  long long S;
  for (int i = 1; i <= 9; i++)
    for (int j = 1; j <= 9; j++)
      for (int k = 1; k <= 9; k++) {
        S = 0;
        for (int pas = 18; pas >= 1; pas--)
          if (st[1] == pas)
            S = 1LL * S * 10 + i;
          else if (st[2] == pas)
            S = 1LL * S * 10 + j;
          else if (st[3] == pas)
            S = 1LL * S * 10 + k;
          else
            S = 1LL * S * 10;
        ans[++dim] = S;
      }
}
void Back3(int top) {
  if (top == 4)
    Build3();
  else
    for (int i = 1 + st[top - 1]; i <= 18; i++) {
      st[top] = i;
      Back3(top + 1);
    }
}
inline void Build2() {
  long long S;
  for (int i = 1; i <= 9; i++)
    for (int j = 1; j <= 9; j++) {
      S = 0;
      for (int pas = 18; pas >= 1; pas--)
        if (st[1] == pas)
          S = 1LL * S * 10 + i;
        else if (st[2] == pas)
          S = 1LL * S * 10 + j;
        else
          S = 1LL * S * 10;
      ans[++dim] = S;
    }
}
void Back2(int top) {
  if (top == 3)
    Build2();
  else
    for (int i = 1 + st[top - 1]; i <= 18; i++) {
      st[top] = i;
      Back2(top + 1);
    }
}
inline void Build1() {
  long long S;
  for (int i = 1; i <= 9; i++) {
    S = 0;
    for (int pas = 18; pas >= 1; pas--)
      if (st[1] == pas)
        S = 1LL * S * 10 + i;
      else
        S = 1LL * S * 10;
    ans[++dim] = S;
  }
}
void Back1(int top) {
  if (top == 2)
    Build1();
  else
    for (int i = 1 + st[top - 1]; i <= 18; i++) {
      st[top] = i;
      Back1(top + 1);
    }
}
inline int Binary_Search(long long x) {
  int left = 1, right = dim, middle, poz = 0;
  while (left <= right) {
    middle = (left + right) / 2;
    if (ans[middle] <= x) {
      poz = middle;
      left = middle + 1;
    } else
      right = middle - 1;
  }
  return poz;
}
int main() {
  int q;
  long long x, y;
  Back3(1);
  for (int i = 1; i <= 4; i++) st[i] = 0;
  Back2(1);
  for (int i = 1; i <= 4; i++) st[i] = 0;
  Back1(1);
  ans[++dim] = 1e18;
  sort(ans + 1, ans + dim + 1);
  cin >> q;
  while (q--) {
    cin >> x >> y;
    x--;
    cout << Binary_Search(y) - Binary_Search(x) << "\n";
  }
  return 0;
}