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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class C {

	public static void main(String[] args) {
		FastScanner scan = new FastScanner();	
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt();
		for(int i = 0; i < n; i++) {
			l = scan.nextLong()-1; r = scan.nextLong();
			in = Long.toString(l).toCharArray();
			len = Long.toString(l).length();
			dp = new Long[len][4][2];
			long lr = go(0, 0, 1);
			in = Long.toString(r).toCharArray();
			len = Long.toString(r).length();
			dp = new Long[len][4][2];
			long rr = go(0, 0, 1);
			out.println(rr-lr);
		}
		out.close();
	}
	
	static long l, r;
	static int len;
	static char[] in;
	static Long[][][] dp;
	
	static long go(int at, int k, int f) {
		if(at == len) return 1;
//		System.out.println(at+" "+k+" "+f+" "+l);
		if(dp[at][k][f] != null) return dp[at][k][f];
		long res = 0;
		if(f == 0) {
			for(int i = 0; i <= 9; i++) {
				if(k < 3 || (k == 3 && i == 0)) res += go(at+1, k+(i==0?0:1), f);
			}
		} else {
			for(int i = 0; i <= in[at]-'0'; i++) {
				if(k < 3 || (k == 3 && i == 0)) res += go(at+1, k+(i==0?0:1), i==(in[at]-'0')?1:0);
			}
		}
		return dp[at][k][f] = res;
	}
	
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}

		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}

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

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

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

		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}

		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}

		public long[] nextLongArray(int n){
			long[] a = new long[n];
			for(int i = 0; i < n; i++) a[i] = nextLong();
			return a;
		}

		public double[] nextDoubleArray(int n){
			double[] a = new double[n];
			for(int i = 0; i < n; i++) a[i] = nextDouble();
			return a;
		}

		public char[][] nextGrid(int n, int m){
			char[][] grid = new char[n][m];
			for(int i = 0; i < n; i++) grid[i] = next().toCharArray();
			return grid;
		}
	}


}