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:
//package com.company;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner(System.in);
//        MyScanner sc = new MyScanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
        TIME_START = System.currentTimeMillis();
        Task.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
//        pw.println("Time used: " + (TIME_END - TIME_START) + ".");
        pw.close();
    }
    //UVALive 6042
    // Bee Tower
    public static class Task {
        static int[] actualToMod;
        static int gcd(int a, int b){
            while (b != 0) {
                a %= b;
                if (a == 0) return b;
                b %= a;
            }
            return a;
        }
        static int gcm(int a, int b) {
            return a / gcd(a, b) * b;
        }
        static long[][][] dp;
        static int[] num;
        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            dp = new long[20][1 << 7][2521];
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp[i].length; j++) {
                    Arrays.fill(dp[i][j], -1);
                }
            }
            num = new int[20];
            actualToMod = new int[2521];
            precompute();
            int T = sc.nextInt();
            while (T-- > 0) {
                long a = sc.nextLong();
                long b = sc.nextLong();
                pw.println(solve(b) - solve(a - 1));
            }
        }
        public static void precompute(){
            int[] calc = new int[2521];
            for (int t = 1; t <= 2520; t++) {
                int i = t;
                int m2 = 0, m3 = 0, m5 = 0, m7 = 0;
                int act = 1;
                while (i % 2 == 0 && m2 < 3) {
                    m2++;
                    i/=2;
                    act *= 2;
                }
                while (i % 3 == 0 && m3 < 2) {
                    m3++;
                    i/=3;
                    act *= 3;
                }
                if (i % 5 == 0) {
                    m5++; act *= 5;
                }
                if (i % 7 == 0) {
                    m7++; act *= 7;
                }
                int hash = 0;
                for (int j = 0; j < m2; j++) {
                    hash += 1 << (4 + j);
                }
                for (int j = 0; j < m3; j++) {
                    hash += 1 << (2 + j);
                }
                for (int j = 0; j < m5; j++) {
                    hash += 1 << (1 + j);
                }
                for (int j = 0; j < m7; j++) {
                    hash += 1 << j;
                }
                if (calc[act] == 0) {
                    for (int j = 0; j < 2520; j++) {
                        if (j % act == 0){
                            dp[0][hash][j] = 1;
                        } else {
                            dp[0][hash][j] = 0;
                        }
                    }
                    calc[act] = 1;
                }
                actualToMod[t] = hash;
            }
        }
        public static long solve(long a){
            int idx = 1;
            while (a != 0) {
                num[idx++] = (int) (a % 10);
                a /= 10;
            }
            return digitDP(idx - 1, 1, 0, false);
        }

        public static long digitDP(int place, int modby, int modremainder, boolean good){
            if (dp[place][actualToMod[modby]][modremainder] != -1 && (good || place == 0)) {
                return dp[place][actualToMod[modby]][modremainder];
            }
            int k = good ? 9 : num[place];
            long sum = 0;
            for (int i = 0; i <= k; i++) {
                int newmod = modby;
                if (i != 0) newmod = gcm(modby, i);
                int newremain = (modremainder * 10 + i ) % 2520;
                sum += digitDP(place - 1, newmod, newremain, good || i != k);
            }
            if (good){
                dp[place][actualToMod[modby]][modremainder] = sum;
            }
            return sum;
        }
    }

    static class MyScanner {
        StringTokenizer st;
        BufferedReader br;

        public MyScanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public MyScanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}