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.PrintWriter;
import java.util.Arrays;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.ArrayList;
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;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        MBeautifulNumbers solver = new MBeautifulNumbers();
        solver.solve(1, in, out);
        out.close();
    }

    static class MBeautifulNumbers {
        long[][][][][][][] dp;
        ArrayList<Integer> arrayList;

        private long findIt(int index, int last, int six_mod, int seven_mod, int eight_mod, int nine_mod, int mask, boolean tight) {
            if (index == -1) {
                boolean flag = true;
                if ((mask & (1 << 0)) != 0 && eight_mod != 0 && eight_mod != 2 && eight_mod != 4 && eight_mod != 6)
                    flag = false;
                if ((mask & (1 << 1)) != 0 && six_mod != 0 && six_mod != 3) flag = false;
                if ((mask & (1 << 2)) != 0 && eight_mod != 0 && eight_mod != 4) flag = false;
                if ((mask & (1 << 3)) != 0 && last != 0) flag = false;
                if ((mask & (1 << 4)) != 0 && six_mod != 0) flag = false;
                if ((mask & (1 << 5)) != 0 && seven_mod != 0) flag = false;
                if ((mask & (1 << 6)) != 0 && eight_mod != 0) flag = false;
                if ((mask & (1 << 7)) != 0 && nine_mod != 0) flag = false;
                if (flag) return 1;
                return 0;
            }
            if (dp[index][last][six_mod][seven_mod][eight_mod][nine_mod][mask] != -1 && !tight)
                return dp[index][last][six_mod][seven_mod][eight_mod][nine_mod][mask];
            int limit = tight ? arrayList.get(index) : 9;
            long ans = 0;
            for (int i = 0; i <= limit; i++) {
                boolean newBOund = tight & (i == arrayList.get(index));
                ans += findIt(index - 1, (i == 0 || i == 5 ? 0 : 1), (six_mod * 10 + i) % 6, (seven_mod * 10 + i) % 7, (eight_mod * 10 + i) % 8, (nine_mod * 10 + i) % 9, (i >= 2 ? (mask | (1 << (i - 2))) : mask), newBOund);
            }
            if (!tight) dp[index][last][six_mod][seven_mod][eight_mod][nine_mod][mask] = ans;
            return ans;
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {


            dp = new long[19][2][6][7][8][9][256];
            long a, b;
            int q;
            q = in.scanInt();
            for (int i = 0; i < 19; i++) {
                for (int j = 0; j < 2; j++) {
                    for (int k = 0; k < 6; k++) {
                        for (int l = 0; l < 7; l++) {
                            for (int m = 0; m < 8; m++) {
                                for (int n = 0; n < 9; n++) {
                                    Arrays.fill(dp[i][j][k][l][m][n], -1);
                                }
                            }
                        }
                    }
                }
            }
            for (int jj = 1; jj <= q; jj++) {
                a = in.scanLong();
                b = in.scanLong();
                filArray(b);
                long ans1 = findIt(arrayList.size() - 1, 0, 0, 0, 0, 0, 0, true);
                filArray(a - 1);
                long ans2 = findIt(arrayList.size() - 1, 0, 0, 0, 0, 0, 0, true);
                out.println(ans1 - ans2);

            }
        }

        private void filArray(long a) {
            arrayList = new ArrayList<>();
            while (a > 0) {
                arrayList.add((int) (a % 10));
                a /= 10;
            }
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public long scanLong() {
            long I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

    }
}