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.Arrays;
import java.util.StringTokenizer;

public class CF_1036C_ClassyNumbers {
	static int [] n;
	static long [][][] dp;
	
	static int a(String s) {
		int c=0;
		n= new int[s.length()];
		for (int i = 0; i < n.length; i++) {
			n[i]=s.charAt(i)-'0';
			if(n[i]!=0)
				c++;
		}
		if(c>0 && c<4)
			return -1;
		return 0;
	}
	static long dp(int smaller, int c, int pos) {
		 
		if(c>3)
			return 0;
		if(pos==n.length)
			return (c!=0)? 1:0;
		if(dp[smaller][c][pos]!=-1)
			return dp[smaller][c][pos];
		
		long zero= dp((smaller==1 || 0<n[pos])? 1:0, c, pos+1);
		long c1= 0,c2=0;
		if(smaller==1){
			c1= 9*dp(smaller, c+1,pos+1);
		}else {
			if(n[pos]!=0) {
				c1= dp(0, c+1, pos+1);
				c2= Math.max(n[pos]-1,0)*dp(1, c+1, pos+1);
			}
		}
		return dp[smaller][c][pos]= zero+c1+ c2;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out= new PrintWriter(System.out);
		
		int n= Integer.parseInt(br.readLine());
		while(n-->0) {
			StringTokenizer st= new StringTokenizer(br.readLine());
			String l=st.nextToken(),r=st.nextToken();
			dp= new long [2][4][19];
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 4; j++) {
					Arrays.fill(dp[i][j], -1);
				}
			}

			long a= a(l)+dp(0,0,0);
			a(r);
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 4; j++) {
					Arrays.fill(dp[i][j], -1);
				}
			}
			long b= dp(0,0,0);
			
			out.println(b-a);
			
		}
		out.flush();
		out.close();
	}

}