Problem: Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

Input

The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 ·1018).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).

Examples

Input

1
1 9


Output

9


Input

1
12 15


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long Set(long long N, long long pos) { return N = N | (1 << pos); }
long long reset(long long N, long long pos) { return N = N & ~(1 << pos); }
bool check(long long N, long long pos) { return (bool)(N & (1 << pos)); }
void CI(long long &_x) { scanf("%d", &_x); }
void CO(long long &_x) { cout << _x; }
template <typename T>
void getarray(T a[], long long n) {
  for (long long i = 0; i < n; i++) cin >> a[i];
}
template <typename T>
void prLLIarray(T a[], long long n) {
  for (long long i = 0; i < n - 1; i++) cout << a[i] << " ";
  cout << a[n - 1] << endl;
}
const double EPS = 1e-9;
const long long INF = 0x7f7f7f7f;
long long dr8[8] = {1, -1, 0, 0, 1, -1, -1, 1};
long long dc8[8] = {0, 0, -1, 1, 1, 1, -1, -1};
long long dr4[4] = {0, 0, 1, -1};
long long dc4[4] = {-1, 1, 0, 0};
long long kn8r[8] = {1, 2, 2, 1, -1, -2, -2, -1};
long long kn8c[8] = {2, 1, -1, -2, -2, -1, 1, 2};
vector<long long> digit;
long long dp[22][2520 + 2][50][3];
int vis[22][2520 + 2][50][3];
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int kas = 1;
int hold[2555];
long long rec(long long inx, long long rem, long long lcm, long long eq) {
  if (inx < 0) {
    if (rem % lcm == 0) return 1;
    return 0;
  }
  if (eq == 0 && vis[inx][rem][hold[lcm]][eq] == kas)
    return dp[inx][rem][hold[lcm]][eq];
  long long ans = 0;
  long long mx = 9;
  if (eq == 1ll) mx = digit[inx];
  for (long long i = 0; i <= mx; i++) {
    long long r = (rem * 10) + i;
    r = r % 2520;
    long long LCM = lcm;
    if (i > 1) {
      LCM = (LCM * i) / gcd(LCM, i);
    }
    ans += rec(inx - 1, r, LCM, eq && (i == mx));
  }
  dp[inx][rem][hold[lcm]][eq] = ans;
  vis[inx][rem][hold[lcm]][eq] = kas;
  return ans;
}
long long func(long long num) {
  if (num == 0) return 1;
  digit.clear();
  while (num) {
    digit.push_back(num % 10);
    num /= 10;
  }
  return rec(digit.size() - 1, 0, 1, 1);
}
int main() {
  std::ios::sync_with_stdio(false);
  set<int> S;
  set<int>::iterator it;
  for (int i = 1; i <= 1024; i++) {
    int lcm = 1;
    for (int j = 1; j <= 9; j++) {
      if (i & (1 << j)) lcm = lcm / gcd(lcm, j) * j;
    }
    S.insert(lcm);
  }
  int idd = 0;
  for (it = S.begin(); it != S.end(); it++) {
    hold[*it] = idd++;
  }
  long long t;
  cin >> t;
  while (t--) {
    long long a, b;
    cin >> a >> b;
    long long ans = func(b);
    a--;
    ans -= func(a);
    cout << ans << "\n";
  }
}