Problem: Let's call some positive integer classy if its decimal representation contains no more than 3 non-zero digits. For example, numbers 4, 200000, 10203 are classy and numbers 4231, 102306, 7277420000 are not.

You are given a segment [L; R]. Count the number of classy integers x such that L ≤ x ≤ R.

Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1 ≤ T ≤ 10^4) — the number of segments in a testcase.

Each of the next T lines contains two integers L_i and R_i (1 ≤ L_i ≤ R_i ≤ 10^{18}).

Output

Print T lines — the i-th line should contain the number of classy integers on a segment [L_i; R_i].

Example

Input

4
1 1000
1024 1024
65536 65536
999999 1000001


Output

1000
1
0
2

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws Exception {

		FastScanner scan = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);

		generate(0, 0);
		long[] a = new long[t.size()];
		int j = 0;
		for(long i : t)
			a[j++] = i;
		for(int ttt = scan.nextInt(); ttt > 0; ttt--) {
			long l = scan.nextLong(), r = scan.nextLong();
			int first = Arrays.binarySearch(a, l);
			int second = Arrays.binarySearch(a, r);
			if(first < 0) first = -(first+1);
			if(second < 0) second = -(second+1);
			pw.println(second - first + (l <= a[first] && a[second] <= r ? 1 : 0));
		}
		
		pw.flush();
	}
	
	static final long MX = (long) (1e18) + 1;
	static TreeSet<Long> t = new TreeSet<>();
	
	static void generate(long cur, int nonzero) {
		if(nonzero > 3) return;
		if(t.contains(cur)) return;
		t.add(cur);
		if(cur > MX / 10) return;
		cur *= 10;
		generate(cur, nonzero);
		for(int i = 1; i < 10; i++)
			generate(cur + i, nonzero + 1);
	}
	
	
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() throws Exception {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		public FastScanner(String filename) throws Exception {
			br = new BufferedReader(new FileReader(filename));
			st = new StringTokenizer("");
		}

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

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

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

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

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