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.util.*;


import java.io.*;



public class Main 
{   
	
	static long dp[][][];
	public static void main(String[] args) throws IOException 
	{ 
		 
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer s=new StringTokenizer(br.readLine());
		int tc=Integer.parseInt(s.nextToken());
		while(tc-->0) {
			dp=new long[20][4][2];
			s=new StringTokenizer(br.readLine());
			long l=Long.parseLong(s.nextToken());
			long r=Long.parseLong(s.nextToken());
			for (int i = 0; i < 20; i++) {
	            for (int j = 0; j < 4; j++) {
	                for (int k = 0; k < 2; k++) {
	                    dp[i][j][k] = -1;
	                }
	            }
	        }
			String st="";
			st=r+"";
			long ans=solveD(st,0,0,true);
			l-=1;
			for (int i = 0; i < 20; i++) {
	            for (int j = 0; j < 4; j++) {
	                for (int k = 0; k < 2; k++) {
	                    dp[i][j][k] = -1;
	                }
	            }
	        }
			st=l+"";
			ans-=solveD(st, 0, 0, true);
			pw.println(ans);
		}
		pw.close();
	}
	private static long solveD(String s, int pos, int cnt, boolean tight) {
		// TODO Auto-generated method stub
		if(pos==s.length())
			return 1;
		
		if(dp[pos][cnt][(tight)?1:0]!=-1)
			return dp[pos][cnt][(tight)?1:0];
		
		long ans=0;
		
		long end=(tight)?(s.charAt(pos)-'0'):9;
		
		for(long i = 0; i<=end ;i++){
			long cntupd=cnt;
			if(i>0) 
				 cntupd +=1;
			if(cntupd<=3){
				ans += solveD(s,pos+1,(int)cntupd,tight&(i==end));
			}
		}
		return dp[pos][cnt][(tight)?1:0] = ans;
	}
	
	
}