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.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        int[] precAnswer;
        int[] precMaxRight;
        int[] precMaxLeft;
        int[][] tailMaxLeft;
        int[][] tailMaxRight;
        OutputWriter out;

        {
            precAnswer = new int[1 << 16];
            precMaxLeft = new int[16];
            precMaxRight = new int[16];
            tailMaxLeft = new int[16][1 << 16];
            tailMaxRight = new int[16][1 << 16];
            for (int x = 0; x < (1 << 16); x++) {
                if (x != 0) {
                    precAnswer[x] += precAnswer[x - 1];
                }
                if (isGood(x)) {
                    ++precAnswer[x];
                }

                int mvx = getMaxBit(x);
                if ((x ^ (1L << mvx)) < x) {
                    ++precMaxRight[mvx];
                    ++tailMaxRight[mvx][x];
                }
                for (int mv = mvx + 1; mv <= 15; mv++) {
                    if ((x ^ (1L << mv)) < x) {
                        ++precMaxLeft[mv];
                        ++tailMaxLeft[mv][x];
                    }
                }

                if (x != 0) {
                    for (int mv = 0; mv < 16; mv++) {
                        tailMaxLeft[mv][x] += tailMaxLeft[mv][x - 1];
                        tailMaxRight[mv][x] += tailMaxRight[mv][x - 1];
                    }
                }
            }
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            this.out = out;

            //
            int q = in.readInt();
            for (int i = 0; i < q; i++) {
                long l = Long.parseLong(in.readString(), 16);
                long r = Long.parseLong(in.readString(), 16);
                out.printLine(f(r) - (0 <= l - 1 ? f(l - 1) : 0));
//            out.printLine(bf_f(r) - bf_f(l - 1));
            }
        /**/


//        for (int i = 0; i < 1e4; i++) {
//            f(0xFFFFFFFFFFFFFL);
//        }

//        Random rnd = new Random(1234);
//        for (int i = 0; ; i++) {
////        out.printLine(val);
////        //out.printLine(val, Long.toHexString(val / 16), Long.toHexString(val), bf_f(val / 16), f(val));
////        out.printLine(val, Long.toHexString(val));
//            int val = rnd.nextInt((int) 1e5);
//            if (bf_f(val) != f(val)) {
//                out.printLine("FUCK");
//                return;
//            } else {
//                System.err.println("OK " + Long.toHexString(val));
//            }
//        }

        }

        private boolean isGood(long number) {
            int mv = getMaxBit(number);
            return (number ^ (1L << mv)) < number;
        }

        int[] getBits(long number) {
            IntArrayList vals = new IntArrayList();
            if (number == 0) {
                vals.add(0);
            } else {
                for (; 0 < number; number >>= 4) {
                    vals.add((int) (number & 15));
                }
            }
            return vals.toArray();
        }

        int getMaxBit(long number) {
            int ans = 0;
            for (; 0 < number; number >>= 4) {
                ans = Math.max(ans, (int) (number & 15));
            }
            return ans;
        }

        private long f(final long number) {
            int[] bits = getBits(number);

            long ans = 0;

            ans += precAnswer[(int) Math.min(number, (1 << 16) - 1)];

            for (int pos = 4; pos + 1 < bits.length; pos++) {
                final int c = (pos + 1) - 4;
                for (int mv = 1; mv <= 15; mv++) {
                    long notGreaterMV = mv * IntegerUtils.power(mv + 1, c - 1);
                    long notGreaterMV1 = (mv - 1) * IntegerUtils.power(mv, c - 1);
                    long cur = (notGreaterMV - notGreaterMV1) * (precMaxRight[mv] + precMaxLeft[mv]) +
                            notGreaterMV1 * precMaxRight[mv];
                    ans += cur;
                }
            }

            int maxPref = -1;
            for (int pos = bits.length - 1; 4 <= pos; pos--) {
                for (int cv = pos == bits.length - 1 ? 1 : 0; cv < bits[pos]; cv++) {
                    int c = (pos + 1) - 1 - 4;
                    for (int mv = Math.max(maxPref, cv); mv <= 15; mv++) {
                        long cur;
                        if (mv == Math.max(maxPref, cv)) {
                            cur = IntegerUtils.power(mv + 1, c) * (precMaxRight[mv] + precMaxLeft[mv]);
                        } else {
                            long notGreaterMV = IntegerUtils.power(mv + 1, c);
                            long notGreaterMV1 = IntegerUtils.power(mv, c);
                            cur = (notGreaterMV - notGreaterMV1) * (precMaxRight[mv] + precMaxLeft[mv]) +
                                    notGreaterMV1 * precMaxRight[mv];
                        }
//                    out.printLine(pos, cv, mv, c, cur);
                        ans += cur;
                    }
                }
                maxPref = Math.max(maxPref, bits[pos]);
            }


            if (maxPref != -1) {
//            for (long x = (number >> 16) << 16; x <= number; x++) {
//                if (isGood(x)) {
//                    ++ans;
//                    out.printLine("->", Long.toHexString(x));
//                }
//            }

                int tail = (int) (number & 0xffff);
                for (int mv = maxPref; mv <= 15; mv++) {
                    int cur;
                    if (mv == maxPref) {
                        cur = tailMaxLeft[mv][tail] + tailMaxRight[mv][tail];
                    } else {
                        cur = tailMaxRight[mv][tail];
                    }
                    ans += cur;
//                if (cur != 0) {
//                    out.printLine("->", mv, cur, "  tail:", Long.toHexString(tail));
//                }
                }
            }


            return ans;
        }

    }

    static interface IntList extends IntReversableCollection {
        public abstract int get(int index);

        public abstract void addAt(int index, int value);

        public abstract void removeAt(int index);

        default public IntIterator intIterator() {
            return new IntIterator() {
                private int at;
                private boolean removed;

                public int value() {
                    if (removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }

                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }

                public boolean isValid() {
                    return !removed && at < size();
                }

                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }


        default public void add(int value) {
            addAt(size(), value);
        }

    }

    static interface IntIterator {
        public int value() throws NoSuchElementException;

        public boolean advance();

        public boolean isValid();

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static abstract class IntAbstractStream implements IntStream {

        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                if (first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }


        public boolean equals(Object o) {
            if (!(o instanceof IntStream)) {
                return false;
            }
            IntStream c = (IntStream) o;
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                if (it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }


        public int hashCode() {
            int result = 0;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }

    }

    static interface IntReversableCollection extends IntCollection {
    }

    static interface IntCollection extends IntStream {
        public int size();

        default public void add(int value) {
            throw new UnsupportedOperationException();
        }

        default public int[] toArray() {
            int size = size();
            int[] array = new int[size];
            int i = 0;
            for (IntIterator it = intIterator(); it.isValid(); it.advance()) {
                array[i++] = it.value();
            }
            return array;
        }

        default public IntCollection addAll(IntStream values) {
            for (IntIterator it = values.intIterator(); it.isValid(); it.advance()) {
                add(it.value());
            }
            return this;
        }

    }

    static class IntArrayList extends IntAbstractStream implements IntList {
        private int size;
        private int[] data;

        public IntArrayList() {
            this(3);
        }

        public IntArrayList(int capacity) {
            data = new int[capacity];
        }

        public IntArrayList(IntCollection c) {
            this(c.size());
            addAll(c);
        }

        public IntArrayList(IntStream c) {
            this();
            if (c instanceof IntCollection) {
                ensureCapacity(((IntCollection) c).size());
            }
            addAll(c);
        }

        public IntArrayList(IntArrayList c) {
            size = c.size();
            data = c.data.clone();
        }

        public IntArrayList(int[] arr) {
            size = arr.length;
            data = arr.clone();
        }

        public int size() {
            return size;
        }

        public int get(int at) {
            if (at >= size) {
                throw new IndexOutOfBoundsException("at = " + at + ", size = " + size);
            }
            return data[at];
        }

        private void ensureCapacity(int capacity) {
            if (data.length >= capacity) {
                return;
            }
            capacity = Math.max(2 * data.length, capacity);
            data = Arrays.copyOf(data, capacity);
        }

        public void addAt(int index, int value) {
            ensureCapacity(size + 1);
            if (index > size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size) {
                System.arraycopy(data, index, data, index + 1, size - index);
            }
            data[index] = value;
            size++;
        }

        public void removeAt(int index) {
            if (index >= size || index < 0) {
                throw new IndexOutOfBoundsException("at = " + index + ", size = " + size);
            }
            if (index != size - 1) {
                System.arraycopy(data, index + 1, data, index, size - index - 1);
            }
            size--;
        }

    }

    static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
        public IntIterator intIterator();

        default public Iterator<Integer> iterator() {
            return new Iterator<Integer>() {
                private IntIterator it = intIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Integer next() {
                    int result = it.value();
                    it.advance();
                    return result;
                }
            };
        }

        default public int compareTo(IntStream c) {
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                int i = it.value();
                int j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class IntegerUtils {
        public static long power(long base, long exponent) {
            if (exponent == 0) {
                return 1;
            }
            long result = power(base, exponent >> 1);
            result = result * result;
            if ((exponent & 1) != 0) {
                result = result * base;
            }
            return result;
        }

    }
}