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;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
template <typename T>
void read(T &x) {
  cin >> x;
}
template <typename T, typename T0>
void read(T &x, T0 &y) {
  cin >> x >> y;
}
template <typename T, typename T0, typename T1>
void read(T &x, T0 &y, T1 &z) {
  cin >> x >> y >> z;
}
template <typename T, typename T0, typename T1, typename T2>
void read(T &x, T0 &y, T1 &z, T2 &w) {
  cin >> x >> y >> z >> w;
}
template <typename T, typename T0>
void read(pair<T, T0> &p) {
  cin >> p.first >> p.second;
}
template <typename T>
void read(vector<T> &oneD, long long int n) {
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int x;
    read(x);
    oneD.push_back(x);
  }
}
template <typename T>
void read(T oneD[], long long int n) {
  for (long long int i = 0; i < n; i++) {
    read(oneD[i]);
  }
}
template <typename T>
void write(T &x) {
  cout << x << " ";
}
template <typename T, typename T0>
void write(T &x, T0 &y) {
  cout << x << " " << y << "\n";
}
template <typename T, typename T0, typename T1>
void write(T &x, T0 &y, T1 &z) {
  cout << x << " " << y << " " << z << "\n";
}
template <typename T, typename T0, typename T1, typename T2>
void write(T &x, T0 &y, T1 &z, T2 &w) {
  cout << x << " " << y << " " << z << " " << w << "\n";
}
template <typename T, typename T0>
void write(pair<T, T0> &p) {
  write(p.first);
  write(p.second);
  cout << endl;
}
template <typename T>
void write(vector<T> &oneD, long long int n) {
  for (long long int i = 0; i < n; i++) {
    cout << oneD[i] << " ";
  }
  cout << endl;
}
template <typename T>
void write(T oneD[], int n) {
  for (long long int i = 0; i < n; i++) {
    write(oneD[i]);
  }
  cout << endl;
}
template <typename T, typename T0>
void write(map<T, T0> &mpp) {
  for (auto it : mpp) {
    write(it.first);
    cout << ": ";
    write(it.second);
    cout << "\n";
  }
  cout << endl;
}
vector<long long int> seive;
void Seive() {
  const long long int maxn = 1e6 + 5;
  seive.resize(maxn);
  for (long long int(i) = 0; (i) < (maxn); ++(i)) seive[i] = i;
  for (long long int(i) = 2; (i) <= (maxn); (i) += (2)) seive[i] = 2;
  seive[1] = -1;
  seive[0] = -1;
  for (long long int i = 3; i <= maxn; i += 2)
    if (i == seive[i])
      for (long long int j = i * i; j < maxn; j += i)
        if (seive[j] == j) seive[j] = i;
}
long long int extended_GCD(long long int a, long long int b, long long int &x,
                           long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int find_x_CRT(long long int num[], long long int rem[],
                         long long int n) {
  long long int pro = 1;
  for (long long int(i) = 0; (i) < (n); ++(i)) pro *= num[i];
  long long int res = 0;
  for (long long int(i) = 0; (i) < (n); ++(i)) {
    long long int pp = pro / num[i];
    res += (rem[i] * modinv(pp, num[i]) * pp);
  }
  res %= pro;
  return res;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int powe(long long int a, long long int b,
                   long long int m = 1000000007) {
  long long int res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
string getString(char x) {
  string s(1, x);
  return s;
}
void precompute_NCR(vector<long long int> &fact) {
  long long int n = 1e6 + 5;
  fact[0] = 1;
  for (long long int(i) = 1; (i) <= ((n - 1)); (i) += (1)) {
    long long int y = (i % 1000000007 * fact[i - 1] % 1000000007) % 1000000007;
    fact[i] = y;
  }
}
long long int NCR(vector<long long int> &fact, long long int N, long long int R,
                  long long int mod = 1000000007) {
  long long int n = fact[N];
  long long int r = fact[R];
  long long int n_r = fact[N - R];
  long long int y = (r % mod * n_r % mod) % mod;
  long long int z = modinv(y, mod);
  long long int ans = (n % mod * z % mod) % mod;
  return ans;
}
void shuru_karte_hai_bina_kise_bakchodi_ke() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
}
string A;
long long int dp[19][4][2] = {};
long long int recur(long long int idx, long long int cnt, long long int tight) {
  if (idx == A.length()) {
    if (cnt <= 3) return 1;
    return 0;
  }
  if (cnt > 3) return 0;
  if (dp[idx][cnt][tight] != -1) return dp[idx][cnt][tight];
  long long int end = tight ? (A[idx] - '0') : 9;
  long long int ans = 0;
  for (long long int(i) = 0; (i) <= (end); (i) += (1)) {
    ans += recur(idx + 1, (cnt + (i > 0)), (tight & (i == end)));
  }
  dp[idx][cnt][tight] = ans;
  return ans;
}
int main() {
  shuru_karte_hai_bina_kise_bakchodi_ke();
  long long int t;
  read(t);
  while (t--) {
    long long int a, b;
    read(a, b);
    a--;
    string x = to_string(a);
    string y = to_string(b);
    long long int ma =
        max((long long int)(x.length()), (long long int)(y.length()));
    memset(dp, -1, sizeof(dp));
    while (x.length() < ma) {
      x = "0" + x;
    }
    while (y.length() < ma) {
      y = "0" + y;
    }
    A = x;
    long long int f1 = recur(0, 0, 1);
    A = y;
    memset(dp, -1, sizeof(dp));
    long long int f2 = recur(0, 0, 1);
    cout << (f2 - f1) << "\n";
  }
  return 0;
}