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.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	public static void main(String[] args) throws IOException {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
					long tm0 = System.currentTimeMillis();
					new Main().run();
					long tm1 = System.currentTimeMillis();
					System.err.println((tm1 - tm0) + " ms");
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	int LCM = 5 * 7 * 8 * 9;
	int[] ind;
	
	int MAXL = 19;
	int MAXM = 48;
	long[] pow10 = new long [MAXL + 1];
	int[] lcm = new int [MAXM];
	long[] dp = new long [(MAXL + 1) * LCM * MAXM];
	long[] cdp = new long [(MAXL + 1) * LCM * MAXM];
	long[] count = new long [MAXL + 1];
	int[] nextRest = new int [(MAXL + 1) * LCM * 10];
	int[] nextInd = new int [MAXM << 4];
	int lcmCount = 0;
	
	int M1 = LCM * MAXM;
	int M2 = MAXM;
	
	int R1 = LCM * 10;
	int R2 = 10;
	
	void run() throws IOException {
		pow10[0] = 1L;
		for (int l = 1; l < MAXL; l++)
			pow10[l] = pow10[l - 1] * 10L;
		ind = new int [LCM + 1];
		fill(ind, -1);
		for (int i = 0; i < 1024; i++)
			if (lcm(i) != 0)
				if (ind[lcm(i)] == -1) {
					lcm[lcmCount] = lcm(i);
					ind[lcm(i)] = lcmCount++;
				}
		for (int l = 0; l < MAXL; l++)
			for (int r = 0; r < LCM; r++)
				for (int d = 0; d < 10; d++)
					nextRest[(l + 1) * R1 + r * R2 + d] = (int) ((pow10[l] * d + r) % LCM);
		for (int m = 0; m < MAXM; m++)
			for (int d = 0; d < 10; d++)
				nextInd[(m << 4) | d] = d < 2 ? m : ind[lcm(lcm[m], d)];
		dp[0 * M1 + 0 * M2 + 0] = 1L;
		for (int l = 0; l < MAXL; l++)
			for (int r = 0; r < LCM; r++)
				for (int m = 0; m < MAXM; m++)
					if (dp[l * M1 + r * M2 + m] != 0L)
						for (int d = 0; d < 10; d++)
							dp[(l + 1) * M1 + nextRest[(l + 1) * R1 + r * R2 + d] * M2 + nextInd[(m << 4) | d]] += dp[l * M1 + r * M2 + m];
		
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		for (int T = nextInt(); T --> 0; )
			out.println(solve(nextLong(), nextLong()));
		
		out.close();
	}
	
	long solve(long l, long r) {
		return count(r) - count(l - 1);
	}

	long count(long x) {
		fill(cdp, 0L);
		cdp[0 * M1 + 0 * M2 + 0] = 1L;
		long t = x;
		for (int l = 0; l < MAXL && t > 0L; l++, t /= 10L) {
			int cd = (int) (t % 10L);
			for (int r = 0; r < LCM; r++)
				for (int m = 0; m < MAXM; m++) {
					if (dp[l * M1 + r * M2 + m] != 0L)
						for (int d = 0; d < cd; d++)
							cdp[(l + 1) * M1 + nextRest[(l + 1) * R1 + r * R2 + d] * M2 + nextInd[(m << 4) | d]] += dp[l * M1 + r * M2 + m];
					if (cdp[l * M1 + r * M2 + m] != 0L)
						cdp[(l + 1) * M1 + nextRest[(l + 1) * R1 + r * R2 + cd] * M2 + nextInd[(m << 4) | cd]] += cdp[l * M1 + r * M2 + m];
				}
		}
		long ret = 0L;
		int len = len(x);
		for (int r = 0; r < LCM; r++)
			for (int m = 0; m < MAXM; m++)
				if (m == 0 || r % lcm[m] == 0)
					ret += cdp[len * M1 + r * M2 + m];
		return ret;
	}

	int len(long x) {
		int ret = 0;
		while (x > 0L) {
			ret++;
			x /= 10L;
		}
		return ret;
	}

	int[] lst = new int [10];
	int lcm(int mask) {
		int sz = 0;
		for (int i = 0; i < 10; i++)
			if ((mask | (1 << i)) == mask)
				lst[sz++] = i;
		if (sz == 0)
			return 0;
		int lcm = lst[0];
		for (int i = 1; i < sz; i++)
			lcm = lcm(lcm, lst[i]);
		return lcm;
	}

	int lcm(int a, int b) {
		return a / gcd(a, b) * b;
	}

	int gcd(int a, int b) {
		while (a > 0 && b > 0)
			if (a > b)
				a %= b;
			else
				b %= a;
		return a + b;
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
}