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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Collections;
import java.io.InputStream;
import java.util.ArrayList;
/**
 * 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);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        int MAXDIGITS = 19;
        int[] lowerBound;
        int[] upperBound;
        long[] dpMem = new long[MAXDIGITS * 48 * 2 * 2 * 7 * 9 * 2 * 10];
        int[][] addUsedMem = new int[48][10];
        int[] compressMem = new int[(1 << 10)];
        int[] uncompressMem = new int[(1 << 10)];
        int[] worksMem = new int[48 * 7 * 9 * 2 * 10 * 10];

        long dp(int index, int compressed, boolean strictlyMore, boolean strictlyLess, int mod7, int mod9, int twoParitySecondToLast, int lastDigit) {
            int memI = index + 19 * (compressed + 48 * ((strictlyMore ? 1 : 0) + 2 * ((strictlyLess ? 1 : 0) + 2 * (mod7 + 7 * (mod9 + 9 * (twoParitySecondToLast + 2 * lastDigit))))));
            if (dpMem[memI] != -1) return dpMem[memI];
            long res = 0;
            for (int here = 0; here <= 9; here++) {
                if ((strictlyMore || here >= lowerBound[index]) && (strictlyLess || here <= upperBound[index])) {
                    if (index == MAXDIGITS - 1) {
                        boolean works = works(addUsed(compressed, here), mod7, mod9, twoParitySecondToLast, lastDigit, here);
                        if (works) {
                            res++;
                        }
                    } else {
                        boolean newStrictlyMore = strictlyMore || here > lowerBound[index];
                        boolean newStrictlyLess = strictlyLess || here < upperBound[index];
                        res += dp(index + 1, addUsed(compressed, here), newStrictlyMore, newStrictlyLess, ((mod7 + here) * 3) % 7, (mod9 + here) % 9, lastDigit % 2, here);
                    }
                }
            }
            return dpMem[memI] = res;
        }

        private int addUsed(int compressed, int here) {
            if (addUsedMem[compressed][here] != -1) return addUsedMem[compressed][here];
            int uncompressed = uncompress(compressed);
            if (here != 6) return addUsedMem[compressed][here] = compress(uncompressed | (1 << here));
            return addUsedMem[compressed][here] = compress((uncompressed | (1 << 2)) | (1 << 3));
        }

        private int compress(int uncompressed) {
            if (compressMem[uncompressed] != -1) return compressMem[uncompressed];
            int twoPower = 0; // [0, 3]
            int threePower = 0; // [0, 2]
            int fivePower = 0; // [0, 1]
            int sevenPower = 0; // [0, 1]
            for (int i = 2; i < 10; i++) {
                if (((uncompressed >> i) & 1) == 1) {
                    if (i == 2) twoPower = 1;
                    if (i == 4) twoPower = 2;
                    if (i == 8) twoPower = 3;
                    if (i == 3) threePower = 1;
                    if (i == 9) threePower = 2;
                    if (i == 5) fivePower = 1;
                    if (i == 7) sevenPower = 1;
                }
            }
            int res = twoPower;
            res += 4 * threePower;
            res += 4 * 3 * fivePower;
            res += 4 * 3 * 2 * sevenPower;
            return compressMem[uncompressed] = res;
        }

        private int uncompress(int compressed) {
            if (uncompressMem[compressed] != -1) return uncompressMem[compressed];
            int originalCompressed = compressed;
            int res = 0;
            int twoPower = compressed % 4;
            if (twoPower == 1) res |= (1 << 2);
            if (twoPower == 2) res |= (1 << 4);
            if (twoPower == 3) res |= (1 << 8);
            compressed /= 4;
            int threePower = compressed % 3;
            if (threePower == 1) res |= (1 << 3);
            if (threePower == 2) res |= (1 << 9);
            compressed /= 3;
            int fivePower = compressed % 2;
            if (fivePower == 1) res |= (1 << 5);
            compressed /= 2;
            int sevenPower = compressed % 2;
            if (sevenPower == 1) res |= (1 << 7);
            compressed /= 2;
            return uncompressMem[originalCompressed] = res;
        }

        private boolean works(int compressed, int mod7, int mod9, int twoParitySecondToLast, int lastDigit, int here) {
            int memI = compressed + 48 * (mod7 + 7 * (mod9 + 9 * (twoParitySecondToLast + 2 * (lastDigit + 10 * here))));
            if (worksMem[memI] != -1) return worksMem[memI] == 1;
            worksMem[memI] = 0;
            int mask = uncompress(compressed);
            for (int usedDigit = 2; usedDigit < 10; usedDigit++) {
                if (((mask >> usedDigit) & 1) == 1) {
                    if (usedDigit == 2) {
                        if (here % 2 != 0) return false;
                    }
                    if (usedDigit == 3) {
                        if ((mod9 + here) % 3 != 0) return false;
                    }
                    if (usedDigit == 4) {
                        int lastTwo = lastDigit * 10 + here;
                        if (lastTwo % 4 != 0) return false;
                    }
                    if (usedDigit == 5) {
                        if (here % 5 != 0) return false;
                    }
                    if (usedDigit == 7) {
                        if ((mod7 + here) % 7 != 0) return false;
                    }
                    if (usedDigit == 8) {
                        int lastTwo = lastDigit * 10 + here;
                        if (twoParitySecondToLast == 0) {
                            if (lastTwo % 8 != 0) return false;
                        } else {
                            if ((lastTwo + 4) % 8 != 0) return false;
                        }
                    }
                    if (usedDigit == 9) {
                        if ((mod9 + here) % 9 != 0) return false;
                    }
                }
            }
            worksMem[memI] = 1;
            return true;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            Arrays.fill(compressMem, -1);
            Arrays.fill(uncompressMem, -1);
            Arrays.fill(worksMem, -1);
            ArrayUtils.fill(addUsedMem, -1);
            int tests = in.readInt();
            for (int test = 0; test < tests; test++) {
                long l = in.readLong();
                long r = in.readLong();
                lowerBound = toArr(l);
                upperBound = toArr(r);
                Arrays.fill(dpMem, -1);
                long res = dp(0, 0, false, false, 0, 0, 0, 0);
                out.printLine(res);
            }
        }

        private int[] toArr(long n) {
            ArrayList<Integer> al = new ArrayList<>();
            while (n > 0) {
                al.add((int) (n % 10));
                n /= 10;
            }
            while (al.size() < MAXDIGITS) al.add(0);
            Collections.reverse(al);
            int[] res = new int[al.size()];
            for (int i = 0; i < res.length; i++) res[i] = al.get(i);
            return res;
        }
    }
    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 long readLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long 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 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 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 ArrayUtils {
        public static void fill(int[][] array, int value) {
            for (int[] row : array) {
                Arrays.fill(row, value);
            }
        }
    }
}