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.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//  WeekOfCode21

public class Solution {
	public static InputReader in;
	public static PrintWriter out;
	public static Random ra = new Random(0);

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		in = new InputReader(inputStream);
//		out = new PrintWriter(outputStream, true);
		out = new PrintWriter(outputStream, false); // enable this for ludicrous speed

		beautifulNumbers();
//		testBM();
//		borrowingMoney();
//		lazySorting();
//		testLazySorting();
//		luckBalance();
//		kangaroo();

		out.close();
	}

	static void beautifulNumbers() {
		int cnt = 0;
		for(int i=1; i<=MOD; i++)
			if(MOD%i == 0)
				Hash[i] = cnt++;

		for(int i=0; i < dp.length; i++) {
			for(int j=0; j < dp[0].length; j++) {
				Arrays.fill(dp[i][j], -1);
			}
		}

		int ts = in.nextInt();
		for (int t = 0; t < ts; t++) {
			long a = in.nextLong();
			long b = in.nextLong();
			System.out.println((solve(b) - solve(a-1)));
		}
	}

	static final int MOD = 2520;
	static long[][][] dp = new long[20][50][2550];
	static int[] dis = new int[20];
	static int[] Hash = new int[2550];

	static long gcd(long a, long b) {
		return b != 0 ? gcd(b,a%b) : a;
	}

	static long dfs(int len, int num, int lcm, boolean flag) {
		if(len < 0) return (num%lcm == 0) ? 1: 0;
		if(!flag && dp[len][Hash[lcm]][num] != -1) {
			return dp[len][Hash[lcm]][num];
		}
		long ans = 0;
		int end = flag?dis[len]:9;
		for(int i=0; i<=end; i++)
			ans += dfs(len-1, (num*10+i)%MOD, (int)(i != 0 ? lcm*i/gcd(lcm,i) : lcm), flag && i==end);
		if(!flag) dp[len][Hash[lcm]][num] = ans;
		return ans;
	}

	static long solve(long n) {
		int pos = 0;
		while(n > 0) {
			dis[pos++] = (int)(n%10L);
			n /= 10L;
		}
		return dfs(pos-1, 0, 1, true);
	}

	public static void testBM() {
		long t1 = System.currentTimeMillis();
		for (int test = 0; test < 1000000; test++) {
			int N = ra.nextInt(10)+1;
			int M = ra.nextInt(N*(N-1)/2 +1);
			boolean[][] g = new boolean[N][N];
			int[] cost = new int[N];
			for (int i = 0; i < cost.length; i++) {
				cost[i] = ra.nextInt(100);
			}
			for (int i = 0; i < M && N > 1; i++) {
				int a = ra.nextInt(N);
				int b = ra.nextInt(N);
				while (a == b) {
					a = ra.nextInt(N);
					b = ra.nextInt(N);
				}
				g[a][b] = true;
				g[b][a] = true;
			}
			String r1 = borrowingMoneySlow(N, g, cost);
			String r2 = borrowingMoney(N, g, cost);
			if (!r1.equals(r2)) {
				System.out.println("fail");
				borrowingMoneySlow(N, g, cost);
				borrowingMoney(N, g, cost);
			}
		}
		System.out.println(System.currentTimeMillis() - t1);
	}

	public static void borrowingMoney() {
		int N = 0;
		boolean[][] g;
		int[] cost;

		N = in.nextInt();
		int m = in.nextInt();
		cost = in.nextIntArray(N);
		g = new boolean[N][N];

		for (int i = 0; i < m; i++) {
			int a = in.nextInt()-1;
			int b = in.nextInt()-1;
			g[a][b] = true;
			g[b][a] = true;
		}

		System.out.println(borrowingMoney(N, g, cost));
//		System.out.println(borrowingMoneySlow(N, g, cost));

	}

	public static String borrowingMoneySlow(int ns, boolean[][] g, int[] cost) {
		int len = ns;
		int N = 1 << len;
		int[] costF = new int[100*35 +1];
		for (int n = 0; n < N; n++) {
			boolean[] active = new boolean[len];
			for (int i = 0; i < len; i++) {
				if (((1 << i) & n) != 0) {
					active[i] = true;
				}
			}
			int sum = 0;
			boolean v = true;
			for (int i = 0; i < ns; i++) {
				if (!active[i]) {
					for (int j = 0; j < ns; j++) {
						if (g[i][j] && !active[j]) {
							v = false;
							break;
						}
					}
					sum += cost[i];
				}
				if (!v) {
					if (i >= 1) {
						System.currentTimeMillis();
					}
					break;
				}
			}
			if (v) {
				costF[sum]++;
			}
		}
		for (int i = costF.length-1; i >= 0; i--) {
			if (costF[i] > 0) {
				return i + " " + costF[i];
			}
		}
		return "";
	}

	public static String borrowingMoney(int N, boolean[][] g, int[] cost) {
		boolean[] visit;
		visit = new boolean[N];
		HashMap<Long, Long> F;
		F = new HashMap<>();

		long mx = 0;
		long tw = 1;
		for (int p = 0; p < visit.length; p++) {
			if (!visit[p]) {
				F = new HashMap<>();

				Queue<Integer> q = new LinkedList<>();
				q.add(p);
				boolean start = true;

				while (!q.isEmpty()) {
					int top = q.poll();

					if (!visit[top]) {
						visit[top] = true;
						HashMap<Long, Long> current = F;
						HashMap<Long, Long> oldF = new HashMap<>();
						for (Entry<Long, Long> e: current.entrySet()) {
							oldF.put(e.getKey(), e.getValue());
						}
						if (start) {
							start = false;

							// do nothing
							current.put(0L, 0L);

							// steal here
							current.put(1L << top, (long)cost[top]);
						} else {
							// steal here

							for (Entry<Long, Long> e: oldF.entrySet()) {
								if (!getBit(e.getKey(), top)) {
									boolean stillHere = true;
									for (int i = 0; i < N; i++) {
										// top will have left if someone robbed next door
										if (g[top][i] && getBit(e.getKey(), i)) {
											stillHere = false;
										}
									}
									if (stillHere) {
										long max = e.getValue();
										long fmask = e.getKey() | 1L << top;

										if (max > -1) {
											max += cost[top];
											if (!current.containsKey(fmask) || current.get(fmask) < max) {
												current.put(fmask, max);
											}
										}
									}
								}
							}
						}

						for (int i = 0; i < N; i++) {
							if (g[top][i]) {
								q.add(i);
							}
						}

						// If all of a edge's neighbours have been visited, it's removed from the searchable set
						// and the maximum of all of them are added back because they cannot influence future
						// events.

						for (Entry<Long, Long> e: oldF.entrySet()) {
							if (!getBit(e.getKey(), top)) {
								boolean stillHere = true;
								for (int i = 0; i < N; i++) {
									// top will have left if someone robbed next door
									if (g[top][i] && getBit(e.getKey(), i)) {
										stillHere = false;
									}
								}
								if (stillHere) {
									long max = e.getValue();
									long fmask = e.getKey() | 1L << top;

									if (max > -1) {
										max += cost[top];
										if (!current.containsKey(fmask) || current.get(fmask) < max) {
											current.put(fmask, max);
										}
									}
								}
							}
						}

					}
				}

				long max = -1;
				for (Entry<Long, Long> e: F.entrySet()) {
					if (e.getValue() > max) {
						max = e.getValue();
					}
				}
				long ways = 0;
				for (Entry<Long, Long> e: F.entrySet()) {
					if (e.getValue() == max) {
						ways++;
					}
				}
				mx += max;
				tw *= ways;
			}
		}



		//System.out.println(max + " " + ways + " " + Long.toBinaryString(fmask));

		return (mx + " " + tw);
	}

	public static String borrowingMoney2(int N, boolean[][] g, int[] cost) {
		boolean[] visit;
		visit = new boolean[N];
		HashMap<Long, Long> F;
		F = new HashMap<>();

		long mx = 0;
		long tw = 1;
		for (int i = 0; i < visit.length; i++) {
			if (!visit[i]) {
				F = new HashMap<>();

				dfs(true, i, N, g, visit, cost, F);

				long max = -1;
				long fmask = 0;
				for (Entry<Long, Long> e: F.entrySet()) {
					if (e.getValue() > max) {
						max = e.getValue();
						fmask = e.getKey();
					}
				}
				long ways = 0;
				for (Entry<Long, Long> e: F.entrySet()) {
					if (e.getValue() == max) {
						ways++;
					}
				}
				mx += max;
				tw *= ways;
			}
		}



		//System.out.println(max + " " + ways + " " + Long.toBinaryString(fmask));

		return (mx + " " + tw);
	}


	public static void dfs(boolean start, int top, int N, boolean[][] g, boolean[] visit, int[] cost, HashMap<Long, Long> F) {
		if (!visit[top]) {
			visit[top] = true;
			HashMap<Long, Long> current = F;
			HashMap<Long, Long> oldF = new HashMap<>();
			for (Entry<Long, Long> e: current.entrySet()) {
				oldF.put(e.getKey(), e.getValue());
			}
			if (start) {

				// do nothing
				current.put(0L, 0L);

				// steal here
				long fmask = 0;
				for (int i = 0; i < N; i++) {
					if (g[top][i]) {
						fmask |= 1L << i;
					}
				}
				current.put(fmask, (long)cost[top]);
			} else {
				// steal here

				for (Entry<Long, Long> e: oldF.entrySet()) {
					if (!getBit(e.getKey(), top)) {
						long max = e.getValue();
						long fmask = e.getKey();

						for (int i = 0; i < N; i++) {
							if (g[top][i]) {
								fmask |= 1L << i;
							}
						}
						if (max > -1) {
							max += cost[top];
							if (!current.containsKey(fmask) || current.get(fmask) < max) {
								current.put(fmask, max);
							}
//							if (current.get(fmask) == max) {
//								current.put(fmask, max);
//							}
						}
					}
				}
			}

			for (int i = 0; i < N; i++) {
				if (g[top][i]) {
					dfs(false, i, N, g, visit, cost, F);
				}
			}
		}
	}

	public static int clearBit(int x, int i) {
		return (x & ~(1 << i));
	}

	public static int setBit(int x, int i) {
		return (x | (1 << i));
	}

	public static boolean getBit(long x, int i) {
		return (x & (1L << i)) != 0;
	}

	public static void testLazySorting() {
		int[] a = new int[4];
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < a.length; j++) {
				a[j] = ra.nextInt(10);
			}
			double r1 = slowLazySorting(a.length, a);
			double r2 = lazySorting(a.length, a);
			int t = 0;
			while (Math.abs(r1 - r2) > 0.1 && t < 10) {
				t++;
				r1 = slowLazySorting(a.length, a);
				r2 = lazySorting(a.length, a);
			}
			if (t == 10) {
				System.out.println("fail");
			}
		}
	}

	public static void lazySorting() {
		int n = in.nextInt();
		int[] a = in.nextIntArray(n);
		System.out.println(String.format("%.6f", lazySorting(n, a)));
//		System.out.println(String.format("%.6f", slowLazySorting(n, a)));
	}

	public static double slowLazySorting(int n, int[] a) {
		ArrayList<Integer> b = new ArrayList<>();
		for (int i = 0; i < a.length; i++) {
			b.add(a[i]);
		}
		Arrays.sort(a);
		int sum = 0;
		int games = 1000000;
		for (int i = 0; i < games; i++) {
			boolean wrong = false;
			int time = 0;

			for (int j = 0; j < a.length; j++) {
				if (a[j] != b.get(j)) {
					wrong = true;
					break;
				}
			}

			while (wrong) {
				wrong = false;
				time++;
				Collections.shuffle(b);
				for (int j = 0; j < a.length; j++) {
					if (a[j] != b.get(j)) {
						wrong = true;
						break;
					}
				}
				if (!wrong) {
					sum += time;
				}
			}
		}
		return sum / (double)games;
	}


	public static double lazySorting(int n, int[] a) {
		int[] f = new int[101];
		int[] b = a.clone();
		Arrays.sort(b);
		if (Arrays.equals(a, b)) {
			return 0;
		}
		for (int i = 0; i < a.length; i++) {
			f[a[i]]++;
		}
		long c = 1;
		for (int i = 1; i <= n; i++) {
			c *= i;
		}
		for (int i = 0; i < f.length; i++) {
			while (f[i] > 0) {
				c /= f[i];
				f[i]--;
			}
		}
		double p = 1.0/c;
		return 1/p;
	}

	public static void luckBalance() {
		int n = in.nextInt();
		int k = in.nextInt();
		int[] luck = new int[n];
		int[] imp = new int[n];
		for (int i = 0; i < n; i++) {
			luck[i] = in.nextInt();
			imp[i] = in.nextInt();
		}
		System.out.println(luckBalance(n, k, luck, imp));
	}

	public static long luckBalance(int n, int k, int[] luck, int[] imp) {
		ArrayList<Integer> important = new ArrayList<>();
		long balance = 0;
		for (int i = 0; i < imp.length; i++) {
			if (imp[i] == 1) {
				important.add(luck[i]);
			} else {
				balance += luck[i];
			}
		}
		Collections.sort(important);
		Collections.reverse(important);
		for (int i = 0; i < important.size(); i++) {
			if (i < k) {
				balance += important.get(i);
			} else {
				balance -= important.get(i);
			}
		}
		return balance;
	}

	public static void kangaroo() {
		int x1 = in.nextInt();
		int v1 = in.nextInt();
		int x2 = in.nextInt();
		int v2 = in.nextInt();
		if (kangaroo(x1, v1, x2, v2)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}

	public static boolean kangaroo(int x1, int v1, int x2, int v2) {
		int dx = x1-x2;
		int dv = v2-v1;
		if (dv == 0) {
			return dx == 0;
		}
		if (((Math.abs(dx) % Math.abs(dv)) == 0) && dx / (double)dv > 0) {
			return true;
		} else {
			return false;
		}
	}

	@SuppressWarnings("serial")
	public static class Counter<T> extends HashMap<T, Integer> {
		public Counter() {
			super();
		}
		public void add(T key) {
			this.add(key, 1);
		}
		public void add(T key, int count) {
			Integer i = this.get(key);
			if (i == null) {
				this.put(key, count);
			} else {
				this.put(key, i+count);
			}
		}
	}

	public static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < a.length; i++) a[i] = this.nextLong();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < a.length; i++) a[i] = this.nextInt();
			return a;
		}
	}
}