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;
const long double eps = 1e-10;
const int inf = 1000000010;
const int mod = 1000 * 1000 * 1000 + 7;
const int MAXN = 1952600;
signed long long T, L, R, ans, num, numm;
signed long long a, b, c, ttt, x;
signed long long A[MAXN];
signed long long B[MAXN];
int X[18];
signed long long f() {
  signed long long out = 0, x = 1;
  for (int i = 0; i < 18; i++) {
    out += X[17 - i] * x;
    x *= 10;
  }
  return out;
}
int main() {
  ios_base::sync_with_stdio(false);
  R = 1000000000000000000;
  A[ttt++] = R;
  for (a = 1; a < 10; a++) {
    for (int i = 0; i < 18; i++) {
      X[i] = a;
      A[ttt++] = f();
      for (b = 1; b < 10; b++) {
        for (int j = i + 1; j < 18; j++) {
          X[j] = b;
          A[ttt++] = f();
          for (c = 1; c < 10; c++) {
            for (int k = j + 1; k < 18; k++) {
              X[k] = c;
              A[ttt++] = f();
              X[k] = 0;
            }
          }
          X[j] = 0;
        }
      }
      X[i] = 0;
    }
  }
  sort(A, A + ttt);
  for (int i = 0; i < ttt; i++) B[i] = -A[ttt - i - 1];
  cin >> T;
  for (; T; T--) {
    cin >> L >> R;
    signed long long x = lower_bound(A, A + ttt, L) - A;
    signed long long y = lower_bound(B, B + ttt, -R) - B;
    if (R < L) {
      cout << 0 << endl;
      continue;
    }
    cout << ttt - x - y << endl;
  }
  return 0;
}