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 pi = acos((long double)-1);
void in(initializer_list<int *> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) scanf("%d", *ptr);
}
void in(initializer_list<long long *> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) scanf("%lld", *ptr);
}
void in(initializer_list<double *> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) scanf("%lf", *ptr);
}
void out(initializer_list<int> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%d ", *ptr);
}
void outln(initializer_list<int> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%d\n", *ptr);
}
void out(initializer_list<long long> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%lld ", *ptr);
}
void outln(initializer_list<long long> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%lld\n", *ptr);
}
int in(int &a, int &b, int &c, int &d) {
  return scanf("%d%d%d%d", &a, &b, &c, &d);
}
int in(int &a, int &b, int &c) { return scanf("%d%d%d", &a, &b, &c); }
int in(int &a, int &b) { return scanf("%d%d", &a, &b); }
int in(long long &a, long long &b) { return scanf("%lld%lld", &a, &b); }
int in(long long &a, long long &b, long long &c, long long &d) {
  return scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
}
int in(long long &a, long long &b, long long &c) {
  return scanf("%lld%lld%lld", &a, &b, &c);
}
int in(long long &a) { return scanf("%lld", &a); }
int in(int &a) { return scanf("%d", &a); }
int in(char *s) { return scanf("%s", s); }
int in(char &c) { return scanf("%c", &c); }
void out(int a, bool ln) { printf("%d%c", a, " \n"[ln]); }
void out(long long a, bool ln) { printf("%lld%c", a, " \n"[ln]); }
void out(double a, int digit, bool ln) {
  printf("%.*f%c", digit, a, " \n"[ln]);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 2e6 + 5;
const int maxm = 1e6 + 5;
const long long mod = 1e9 + 7;
int a[maxn], b[maxn], dp[20][5], n;
long long dfs(int pos, int num, bool limit) {
  if (num > 3) return 0;
  if (pos == 0) return 1;
  if (!limit && dp[pos][num] != -1) return dp[pos][num];
  int up = limit ? a[pos] : 9;
  long long ans = 0;
  ans = dfs(pos - 1, num, limit && up == 0);
  for (int i = 1; i <= up; i++) {
    ans += dfs(pos - 1, num + 1, limit && i == up);
  }
  return limit ? ans : dp[pos][num] = ans;
}
int main() {
  memset((dp), (-1), sizeof(dp));
  int TT;
  scanf("%d", &TT);
  for (int TTT = 1; TTT <= TT; TTT++) {
    long long s1, s2;
    cin >> s1 >> s2;
    n = 0;
    while (s2) {
      a[++n] = s2 % 10;
      s2 /= 10;
    }
    long long ans = dfs(n, 0, 1);
    n = 0;
    s1--;
    while (s1) {
      a[++n] = s1 % 10;
      s1 /= 10;
    }
    ans -= dfs(n, 0, 1);
    out(ans, 1);
  }
  return 0;
}