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:
// "static void main" must be defined in a public class.
import java.io.*;
import java.util.*;
public class Main {
    
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    
    public static void main(String[] args) {
        FastReader s = new FastReader();
        int t =s.nextInt();
        while(t-- > 0){
            String start = s.next(), end = s.next();
            System.out.println( countOfClassyNumbers(end) - countOfClassyNumbers( start ) + isStartValid(start) );
        }
    }
    
    public static int isStartValid(String no){
       int count = 0;
        for(int i = 0; i < no.length();i++){
            if(no.charAt(i) != '0')
                count++;
            if(count > 3)
                return 0;
        }
        return 1;
    }
    
    public static long countOfClassyNumbers(String no){
         long[][][] dp = new long[no.length()][4][2];
            for(int i = 0; i < dp.length;i++)
                for(int j = 0; j < dp[0].length;j++)
                    Arrays.fill(dp[i][j], -1);
         return getCount(0, 0, 1, dp, no);
    }
    
    public static long getCount(int pos, int count, int isTight, long[][][] dp, String no){
    	 if(count > 3)
             return 0;
         if( pos == no.length() )
            return 1;
        if(dp[pos][count][isTight] != -1)
            return dp[pos][count][isTight];
        long ans = 0, upperBound = 9;
        if(isTight == 1)
            upperBound = (int)( no.charAt(pos) - '0' );
        for(int i = 0; i <= upperBound;i++){
            int flag = ( i != 0)? 1 : 0, tempTight = 0;
            if(isTight == 1 && i == upperBound)
                tempTight = 1;
            ans += getCount( pos + 1, count + flag, tempTight, dp, no);            
        }
        return dp[pos][count][isTight] = ans;
    }
}