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.lang.*;
import java.io.*;

public class Solution
{
    public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		int k = Integer.parseInt(br.readLine());
		for(int i=0;i<k;i++){
		    StringTokenizer st = new StringTokenizer(br.readLine());
		    long l = Long.parseLong(st.nextToken());
		    int way1 = (l-1 == 0) ?0 : findWays(l-1);
		    long r = Long.parseLong(st.nextToken());
		    int way2 = findWays(r);
		    out.println(way2-way1);
		}
		out.close();
	}
	
	public static int findWays(long l){
	    String b = String.valueOf(l);
	    int ways = 0;
	    int dif = 0;
	    int i = 0;
	    Stack<Integer> st = new Stack();
	    for(;i<b.length()&&dif<3;i++){
	     if(b.charAt(i) != '0'){
	         st.push(i);
	         dif++;
	     }
	   } 
	     
	     if(i<b.length() && dif == 3){
	         l = (long)Math.pow(10,b.length()-i)*Long.parseLong(b.substring(0,i));
	     }
	    b = String.valueOf(l);
	    int n = b.length();
	        while(n > 0){
	        if(!st.isEmpty()){
	        ways++;
             while(!st.isEmpty()){
                int ind = st.pop();
                int val = b.charAt(ind)-'0'-1;
                if(val > 0) ways+= val*permute(b.length()-ind-1,2-st.size());
                if(!st.isEmpty()) ways+= permute(b.length()-ind-1,3-st.size());
              }
              n--;
	       }
	       else{
	           ways+=9*permute(n-1,2);
	           n--;
	        }
	     };
	     return ways;
	}

	
	public static int permute(int n, int k){
	    if(n == 0) return 1;
	    int ways = 0;
	    if(n>=2 && k == 2) ways+= (n*(n-1)/2)*9*9;
	    if(k>=1) ways+= n*9;
	    ways++;
	    
	    return ways;
	}
}