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.math.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);

		Task solver = new Task();
		solver.solve(in, out);

		out.close();
	}
}

class InputReader {
	BufferedReader buff;
	StringTokenizer tokenizer;

	InputReader(InputStream stream) {
		buff = new BufferedReader(new InputStreamReader(stream));
		tokenizer = null;
	}

	String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens())
			try {
				tokenizer = new StringTokenizer(buff.readLine());
			}
			catch (IOException e) {
				throw new RuntimeException(e);
			}
		return tokenizer.nextToken();
	}
	int nextInt() { return Integer.parseInt(next()); }
	long nextLong() { return Long.parseLong(next()); }
}

class Task {
	final static int MAXL = 19;
	final static int[] prim = {2, 3, 5, 7};
	final static int[] pow = {12, 4, 2, 1};
	final static int MAXN = 48;
	final static int MAXM = 252;
	final static int LCM = 2520;
	long[][][] dp;

	int encode(int[] x) {
		int ret = 0;
		for (int i = 0; i < pow.length; ++i)
			ret += x[i] * pow[i];
		return ret;
	}

	int[] decode(int x) {
		int[] ret = new int[4];
		for (int i = 0; i < pow.length; ++i) {
			ret[i] = x / pow[i];
			x %= pow[i];
		}
		return ret;
	}

	int merge(int mask, int x) {
		if (x == 0)
			return mask;
		int[] ret = decode(mask);
		for (int i = 0; i < prim.length; ++i) {
			int cnt = 0;
			while (x % prim[i] == 0) {
				x /= prim[i];
				++cnt;
			}
			ret[i] = Math.max(ret[i], cnt);
		}
		return encode(ret);
	}

	long divTest(int x, int mask) {
		int[] ret = decode(mask);
		for (int i = 0; i < prim.length; ++i) {
			int now = 1;
			for (int j = 0; j < ret[i]; ++j)
				now *= prim[i];
			if (x % now != 0)
				return 0L;
		}
		return 1L;
	}

	long go(long l, long r) {
		int[] a = new int[MAXL], b = new int[MAXL];
		int pos = -1;
		for (int i = 0; i < MAXL; ++i) {
			a[i] = (int)(l % 10);
			b[i] = (int)(r % 10);
			if (a[i] != b[i])
				pos = i;
			l /= 10; r /= 10;
		}

		long ret = 0;
		int[] rem = new int[MAXL], mask = new int[MAXL];
		for (int i = MAXL - 2; i >= 0; --i) {
			rem[i] = (rem[i + 1] + a[i + 1]) * 10 % LCM;
			mask[i] = merge(mask[i + 1], a[i + 1]);
		}

		for (int i = 0; i <= pos; ++i)
			for (int j = a[i] + 1; j < (i == pos ? b[i] : 10); ++j)
				if (i == 0)
					ret += divTest(rem[i] + j, merge(mask[i], j));
				else
					ret += dp[i][merge(mask[i], j)][(rem[i] + j) * 10 % LCM / 10];

		rem = new int[MAXL]; mask = new int[MAXL];
		for (int i = MAXL - 2; i >= 0; --i) {
			rem[i] = (rem[i + 1] + b[i + 1]) * 10 % LCM;
			mask[i] = merge(mask[i + 1], b[i + 1]);
		}
		for (int i = pos - 1; i >= 0; --i)
			for (int j = 0; j < b[i]; ++j)
				if (i == 0)
					ret += divTest(rem[i] + j, merge(mask[i], j));
				else
					ret += dp[i][merge(mask[i], j)][(rem[i] + j) * 10 % LCM / 10];

		return ret;
	}

	void solve(InputReader in, PrintWriter out) {
		dp = new long[MAXL][MAXN][MAXM];
		for (int i = 0; i < MAXN; ++i)
			for (int j = 0; j < MAXM; ++j)
				for (int c = 0; c < 10; ++c)
					dp[1][i][j] += divTest(j * 10 + c, merge(i, c));

		//out.println(Arrays.toString(decode(4)));
		//out.println(dp[1][4][3]);
		for (int i = 2; i < MAXL; ++i)
			for (int j = 0; j < MAXN; ++j)
				for (int k = 0; k < MAXM; ++k)
					for (int c = 0; c < 10; ++c)
						dp[i][j][k] += dp[i - 1][merge(j, c)][(k * 10 + c) * 10 % LCM / 10];

		for (int q = in.nextInt(); q-- > 0; ) {
			long l = in.nextLong(), r = in.nextLong();
			out.println(go(l - 1, r + 1));
		}
	}
}