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


public class classy{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception addd) {
					addd.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception addd) {
				addd.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	
	public static FastReader sc = new FastReader();
 
	static int mod = (int) (1e2),m,n;
	static long[][][] dp ;
	public static void main(String[] args) {

	 int t = sc.nextInt();
	 while(t-->0) {
		 long l = sc.nextLong();
		 long r = sc.nextLong();
		 long ans = solve(r) - solve(l-1);
		 out.println(ans);
	 }
		
	out.close();
}
	private static long solve(long n) {
		 dp = new long[20][4][2];
		 for(int i=0;i<dp.length;++i) {
			for(int j=0;j<dp[i].length;++j)
				Arrays.fill(dp[i][j],-1);
		 }
		 char[] s = String.valueOf(n).toCharArray();
		return f(0,0,1,s);
	}
	private static long f(int i, int cnt,int l,char[] s) {
		//out.println(i+" "+cnt+" "+l);
		if(i == s.length) {
			if(cnt <= 3) return 1;
			return 0;
		}
		if(cnt > 3) return 0;
		if(dp[i][cnt][l] != -1) return dp[i][cnt][l];
		long o1=0;
		int end = (l == 1)?s[i]-'0':9;
		for(int dig=0;dig<=end;++dig) 
			o1 += f(i+1,cnt + (dig!=0?1:0), l&(dig == end?1:0),s);	
		
		//out.println(o1);
		return dp[i][cnt][l] = o1;
	}
	
}