#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
char l[20], r[20];
int rans[1 << 16];
long long get(vector<int> num) {
  long long have[20][2];
  long long ans = 0;
  for (int i = 1; i <= 15; i++) {
    int j;
    int loc = i / 4;
    have[0][1] = 0;
    have[0][0] = 1;
    for (j = 1; j < (int)num.size(); j++) {
      int cnt = i + 1, flag = 1;
      if (j == loc + 1) {
        cnt = 0;
        flag = 0;
        for (int k = 0; k <= i; k++) {
          if (!(k & (1 << (i % 4)))) continue;
          cnt++;
          if (k == i) flag = 1;
        }
      }
      have[j][0] = have[j - 1][0] * cnt;
      have[j][1] = have[j - 1][0] * flag + have[j - 1][1] * (cnt - flag);
    }
    int flag = 0;
    for (j = num.size() - 1; j >= 0; j--) {
      int cnt = 0, rbig = 1, ri = 1;
      if (j != loc)
        cnt = min(i + 1, num[j]);
      else {
        rbig = 0;
        ri = 0;
        for (int k = 0; k <= min(num[j], i); k++) {
          if (!(k & (1 << (i % 4)))) continue;
          if (k != num[j]) cnt++;
          if (k == i) ri = 1;
          if (k == min(num[j], i)) rbig = 1;
        }
      }
      ans += have[j][1 - flag] * cnt;
      if (num[j] > i || rbig == 0) {
        ans += ri * !flag * (have[j][0] - have[j][1]);
        break;
      }
      if (num[j] == i) {
        flag = ri;
      }
    }
    if (j == -1 && flag) ans++;
  }
  return ans;
}
long long get(long long num) {
  if (num <= 0) return 0;
  if (num < 1 << 16) return rans[num];
  vector<int> rv;
  for (; num; rv.push_back(num % 16), num /= 16)
    ;
  return get(rv);
}
int getch(char ch) {
  if (ch <= '9' && ch >= '0')
    return ch - '0';
  else
    return ch - 'a' + 10;
}
long long getnum(char str[]) {
  int l = strlen(str);
  long long ans = 0;
  for (int i = 0; i < l; i++) {
    ans = ans * 16 + getch(str[i]);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  for (int i = 1; i < 1 << 16; i++) {
    rans[i] = rans[i - 1];
    long long rmask = 0;
    for (int j = i; j; j >>= 4) rmask |= 1 << (j % 16);
    if ((i ^ rmask) < i) rans[i]++;
  }
  int nq;
  scanf("%d", &nq);
  for (int i1 = 0; i1 < nq; i1++) {
    scanf("%s%s", l, r);
    long long nl = getnum(l), nr = getnum(r);
    nl--;
    printf("%I64d\n", get(nr) - get(nl));
  }
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

Sherlock found a piece of encrypted data which he thinks will be useful to catch Moriarty. The encrypted data consists of two integer l and r. He noticed that these integers were in hexadecimal form.

He takes each of the integers from l to r, and performs the following operations:

  1. He lists the distinct digits present in the given number. For example: for 101416, he lists the digits as 1, 0, 4. 
  2. Then he sums respective powers of two for each digit listed in the step above. Like in the above example sum = 21 + 20 + 24 = 1910. 
  3. He changes the initial number by applying bitwise xor of the initial number and the sum. Example: <image>. Note that xor is done in binary notation. 



One more example: for integer 1e the sum is sum = 21 + 214. Letters a, b, c, d, e, f denote hexadecimal digits 10, 11, 12, 13, 14, 15, respertively.

Sherlock wants to count the numbers in the range from l to r (both inclusive) which decrease on application of the above four steps. He wants you to answer his q queries for different l and r.

Input

First line contains the integer q (1 ≤ q ≤ 10000).

Each of the next q lines contain two hexadecimal integers l and r (0 ≤ l ≤ r < 1615).

The hexadecimal integers are written using digits from 0 to 9 and/or lowercase English letters a, b, c, d, e, f.

The hexadecimal integers do not contain extra leading zeros.

Output

Output q lines, i-th line contains answer to the i-th query (in decimal notation).

Examples

Input

1
1014 1014


Output

1


Input

2
1 1e
1 f


Output

1
0


Input

2
1 abc
d0e fe23


Output

412
28464

Note

For the second input,

1416 = 2010

sum = 21 + 24 = 18

<image>

Thus, it reduces. And, we can verify that it is the only number in range 1 to 1e that reduces.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
char l[20], r[20];
int rans[1 << 16];
long long get(vector<int> num) {
  long long have[20][2];
  long long ans = 0;
  for (int i = 1; i <= 15; i++) {
    int j;
    int loc = i / 4;
    have[0][1] = 0;
    have[0][0] = 1;
    for (j = 1; j < (int)num.size(); j++) {
      int cnt = i + 1, flag = 1;
      if (j == loc + 1) {
        cnt = 0;
        flag = 0;
        for (int k = 0; k <= i; k++) {
          if (!(k & (1 << (i % 4)))) continue;
          cnt++;
          if (k == i) flag = 1;
        }
      }
      have[j][0] = have[j - 1][0] * cnt;
      have[j][1] = have[j - 1][0] * flag + have[j - 1][1] * (cnt - flag);
    }
    int flag = 0;
    for (j = num.size() - 1; j >= 0; j--) {
      int cnt = 0, rbig = 1, ri = 1;
      if (j != loc)
        cnt = min(i + 1, num[j]);
      else {
        rbig = 0;
        ri = 0;
        for (int k = 0; k <= min(num[j], i); k++) {
          if (!(k & (1 << (i % 4)))) continue;
          if (k != num[j]) cnt++;
          if (k == i) ri = 1;
          if (k == min(num[j], i)) rbig = 1;
        }
      }
      ans += have[j][1 - flag] * cnt;
      if (num[j] > i || rbig == 0) {
        ans += ri * !flag * (have[j][0] - have[j][1]);
        break;
      }
      if (num[j] == i) {
        flag = ri;
      }
    }
    if (j == -1 && flag) ans++;
  }
  return ans;
}
long long get(long long num) {
  if (num <= 0) return 0;
  if (num < 1 << 16) return rans[num];
  vector<int> rv;
  for (; num; rv.push_back(num % 16), num /= 16)
    ;
  return get(rv);
}
int getch(char ch) {
  if (ch <= '9' && ch >= '0')
    return ch - '0';
  else
    return ch - 'a' + 10;
}
long long getnum(char str[]) {
  int l = strlen(str);
  long long ans = 0;
  for (int i = 0; i < l; i++) {
    ans = ans * 16 + getch(str[i]);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  for (int i = 1; i < 1 << 16; i++) {
    rans[i] = rans[i - 1];
    long long rmask = 0;
    for (int j = i; j; j >>= 4) rmask |= 1 << (j % 16);
    if ((i ^ rmask) < i) rans[i]++;
  }
  int nq;
  scanf("%d", &nq);
  for (int i1 = 0; i1 < nq; i1++) {
    scanf("%s%s", l, r);
    long long nl = getnum(l), nr = getnum(r);
    nl--;
    printf("%I64d\n", get(nr) - get(nl));
  }
  return 0;
}

```