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.*;
 
public class edu50_c extends Template{
    public static ArrayList<Long> digits(long l){
        ArrayList<Long> al = new ArrayList<>();
        while(l!=0){
            al.add(l%10); l /= 10;
        }
        Collections.reverse(al);
        return al;
    }

    public static long classy(int in, int i1, int b, ArrayList<Long> al, long[][][] a){
        if(b<0) return 0;
        if(i1>=al.size()) return 1;
        if(a[in][b][i1]!=-1) return a[in][b][i1];
        if(al.get(i1)==0){
            a[in][b][i1] =  classy(in, i1+1, b, al, a);
        }
        else{
            ArrayList<Long> al2 = new ArrayList<>(al);
            for(int i=i1+1; i<al2.size(); i++) al2.set(i, 9L);
            a[in][b][i1] = //classy(i1+1, b, al, a) + 
                            classy(in, i1+1, b-1, al, a)
                     + (al.get(i1)-1)*classy(1, i1+1, b-1, al2, a) + classy(1, i1+1, b, al2, a); 
        }
        return a[in][b][i1];
    }
    public static void main(String[] args) {
        int T = nI();
        for(int t=0; t<T; t++){
            long l = nL(), r = nL();
            ArrayList<Long> al1 = digits(l-1);
            ArrayList<Long> al2 = digits(r);
            long a[][][] = new long[2][4][al1.size()];
            long b[][][] = new long[2][4][al2.size()];
            for(long [][] ll : a) for(long [] xx :ll) Arrays.fill(xx, -1);
            for(long [][] ll : b) for(long [] xx :ll) Arrays.fill(xx, -1);
            long l1 = classy(0, 0, 3, al1, a);
            long l2 = classy(0, 0, 3, al2, b);

            pn(l2 - l1);

        }
    }
}
 
class Template{
    static Scanner s = new Scanner(System.in);
    final static int nI(){return s.nextInt();}
    final static long nL(){return s.nextLong();}
    final static String nS(){return s.nextLine();}
    /* Renaming of some generic utility classes */
    final static class mylist extends ArrayList<pair>{}
    /* Constants Section */
    final static int INT_MIN = Integer.MIN_VALUE ;
    final static int INT_MAX = Integer.MAX_VALUE ;
    final static long LONG_MIN = Long.MIN_VALUE ;
    final static long LONG_MAX = Long.MAX_VALUE ;
    static long MOD = 1000000007 ;
    static void p(){System.out.println();}
    static void pn(long a){System.out.println(a);}
    static void pn(mylist a){System.out.println(a);}
    static void p(long a){System.out.printf("%d ", a);}
    static void p(long a, long b){System.out.printf("%d %d\n", a, b);}
    static void p(long a, long b, long c){System.out.printf("%d %d %d\n", a, b, c);}
    /* Implementation of operations modulo MOD */
    static long inv(long a){ return powM(a,MOD-2) ; }
    static long m(long a,long b){ return (a*b)%MOD ; }
    static long d(long a,long b){ return (a*inv(b))%MOD ; }
    static long powM(long a,long b){
        if(b<0) return powM(inv(a),-b) ;
        long ans=1 ;
        for( ; b!=0 ; a=(a*a)%MOD , b/=2) if((b&1)==1) ans = (ans*a)%MOD ;
        return ans ;
    }
}
class pair implements Comparable<pair>{
    long x ; long y ;
    pair(long _x,long _y){ x=_x ; y=_y ;}
    public int compareTo(pair p){
        return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
    }
    public String toString(){ return "(" + x + " " + y+ ")";}
}