#include <bits/stdc++.h>
using namespace std;
long long dp[17][17][17];
int high_bit(int x) {
  for (int i = 3; i >= 0; i--)
    if ((1 << i) & x) return i + 1;
  return 0;
}
int get_value(char c) {
  if ('0' <= c && c <= '9') return c - '0';
  return c - 'a' + 10;
}
long long get(string n) {
  long long ans = 0;
  for (int l = 1; l < n.size(); l++)
    for (int t = 1; t < 16; t++)
      for (int k = 0; k < 17; k++) {
        int sm = max(k, t + 1);
        int fh = sm;
        if ((l - 1) * 4 > fh - 1) {
        } else if ((l - 1) * 4 + 4 > fh - 1) {
          if (!(t & (1 << ((fh - 1) & 3)))) continue;
          fh = 0;
        }
        ans += dp[l - 1][fh][k];
      }
  int second_max = 0;
  for (int i = 0; i < n.size(); i++) {
    int value = get_value(n[i]);
    int first = 0;
    if (i == 0) first = 1;
    for (int t = first; t < value; t++)
      for (int k = 0; k < 17; k++) {
        int sm = max(second_max, k);
        sm = max(sm, t + 1);
        int fh = sm;
        if (((int)n.size() - i - 1) * 4 > fh - 1) {
        } else if (((int)n.size() - i - 1) * 4 + 4 > fh - 1) {
          if (!(t & (1 << ((fh - 1) & 3)))) continue;
          fh = 0;
        } else {
          if ((int)n.size() - 1 - (fh - 1) / 4 < 0 ||
              !(get_value(n[n.size() - 1 - (fh - 1) / 4]) &
                (1 << ((fh - 1) & 3))))
            continue;
          fh = 0;
        }
        ans += dp[n.size() - i - 1][fh][k];
      }
    second_max = max(second_max, value + 1);
  }
  return ans;
}
string add(string n) {
  int idx = n.size() - 1;
  while (idx >= 0 && n[idx] == 'f') {
    n[idx] = '0';
    idx--;
  }
  if (idx < 0) return "1" + n;
  if (n[idx] == '9')
    n[idx] = 'a';
  else
    n[idx] += 1;
  return n;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  dp[0][0][0] = 1;
  for (int l = 1; l < 17; l++)
    for (int dig = 0; dig < 16; dig++)
      for (int first_has = 0; first_has < 17; first_has++)
        for (int second_max = 0; second_max < 17; second_max++) {
          int nf = first_has;
          if (first_has != 0 && 4 * (l - 1) <= first_has - 1 &&
              first_has - 1 < 4 * l) {
            if (!(dig & (1 << ((first_has - 1) & 3)))) continue;
            nf = 0;
          }
          dp[l][first_has][max(dig + 1, second_max)] +=
              dp[l - 1][nf][second_max];
        }
  int q;
  cin >> q;
  while (q--) {
    string l, r;
    cin >> l >> r;
    cout << get(add(r)) - get(l) << "\n";
  }
  return 0;
}
