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

public class Main {
    static PrintWriter pw;
    static Scanner sc;
    static HashMap<Pair, Integer> map;
    static String end;
    static String st;
    static int inf=(int)1e9;
    static byte[] arr;
    static long[] ans;
    static long ceildiv(long x, long y){ return (x+y-1)/y;}
    public static void main(String[] args) throws Exception {
        sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);
        int t=sc.nextInt();
        tree= new TreeSet<Long>();
        tree.add((long)1e18);
        arr=new byte[18];
        gener(0, 0);
        ans= new long[tree.size()];
        int idx=0;
        for(long x: tree)
            ans[idx++]=x;
        while(t-->0){
            long l=sc.nextLong(), r=sc.nextLong();
            pw.println(smaller(r)-strictsmaller(l));
        }
        pw.close();
    }
    static int smaller(long x) {
        int idx=-1;
        int start=0,end=ans.length-1;
        while(start<=end) {
            int mid=(start+end)/2;
            if(ans[mid]>x) {
                end=mid-1;
            }else {
                idx=mid;
                start=mid+1;
            }
        }
        return idx;
    }
    static int strictsmaller(long x) {
        int idx=-1;
        int start=0,end=ans.length-1;
        while(start<=end) {
            int mid=(start+end)/2;
            if(ans[mid]>=x) {
                end=mid-1;
            }else {
                idx=mid;
                start=mid+1;
            }
        }
        return idx;
    }
    static TreeSet<Long> tree;
    static void gener(int i, int taken){
        if(taken==3 || i==18){
            tree.add(value());
            return;
        }
        for(int j=0; j<9; j++){
            arr[i]=(byte)(1+j);
            gener(i+1, taken+1);
        }
        arr[i]=0;
        gener(i+1, taken);
    }
    static long value(){
        long pow=1l;
        long ans=0l;
        for(int i=0; i<18; i++, pow*=10)
            ans+=arr[17-i]*pow;
        return ans;
    }
//    static boolean check(int i, int j, int l){
//        boolean ans=false;
//        for(int k=0; k<dp[i+1].length && !ans; k++){
//            if(k==j)
//                continue;
//            if(dp[i+1][k]){
//                int max=0;
//                for(int x=k; (x+1)%(p.length)!=j && !ans; x++)
//                    max=Math.max(max, p[(x+1)%(p.length)]);
//                max=Math.max(max, p[j]);
//                ans|=max+arr[i]<=l;
//            }
//        }
//        return ans;
//    }
//    static int LIS(){
//        list= new ArrayList<Integer>();
//        for(int i=0; i<arr.length; i++){
//            int idx=find(arr[i]);
//            if(idx==-1)
//                list.add(i);
//            else
//                list.set(idx, i);
//        }
//        return list.size();
//    }
//    static int find(int x){
//        int st=0, end=list.size()-1;
//        int idx=-1;
//        while(st<=end){
//            int mid=(st+end)/2;
//            if(arr[list.get(mid)]>=x){
//                idx=mid;
//                end=mid-1;
//            }else{
//                st=mid+1;
//            }
//        }
//        return idx;
//    }
    static boolean check(int x){
        int one=0, zero=0;
        for(; x>0; x>>=1){
            if((x&1)==1)
                one++;
            else
                zero++;
        }
        return one!=1 && zero!=0;
    }
    static void printArr(int[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(long[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(Integer[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public int[] nextArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++)
                arr[i] = nextInt();
            return arr;
        }
        public Integer[] nextsort(int n) throws IOException{
            Integer[] arr=new Integer[n];
            for(int i=0; i<n; i++)
                arr[i]=nextInt();
            return arr;
        }
        public Pair nextPair() throws IOException{
            return new Pair(nextInt(), nextInt());
        }
        public Pair[] nextPairArr(int n, int l) throws IOException{
            Pair[] arr=new Pair[n];
            for(int i=0; i<n; i++)
                arr[i]=new Pair(nextInt(), nextInt());
            return arr;
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static class Pair implements Comparable<Pair>{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public int hashCode() {
            return this.x*2000+this.y;
        }
        public int compareTo(Pair p) {
            if(this.y!=p.y)
                return this.y-p.y;
            return this.x-p.x;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair p = (Pair) obj;
            return this.x==p.x && this.y==p.y;
        }
        public boolean equal(Pair p){
            if(this.x==p.x)
                return this.y==p.y;
            if(this.x==p.y)
                return this.y==p.x;
            else
                return false;
        }
        public String toString(){
            return this.x+" "+this.y;
        }
    }
    static class Pair2 implements Comparable<Pair2>{
        int x;
        int y;
        public Pair2(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public int hashCode() {
            return this.x*2000+this.y;
        }
        public int compareTo(Pair2 p) {
            if(this.x!=p.x)
                return this.x-p.x;
            return this.y-p.y;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair2 p = (Pair2) obj;
            return this.x==p.x && this.y==p.y;
        }
        public boolean equal(Pair2 p){
            if(this.x==p.x)
                return this.y==p.y;
            if(this.x==p.y)
                return this.y==p.x;
            else
                return false;
        }
        public String toString(){
            return this.x+" "+this.y;
        }
    }
    static class Triple implements Comparable<Triple>{
        int x;
        int y;
        char c;
        public Triple(int x, int y, char c){
            this.x=x;
            this.y=y;
            this.c=c;
        }
        public int compareTo(Triple t){
            return this.y-t.y;
        }
        public String toString(){
            if(this.x==1)
                return "INSERT "+(this.y+1)+" "+this.c;
            else if(this.x==0)
                return "REPLACE "+(this.y+1)+" "+this.c;
            else
                return "DELETE "+(this.y+1);
        }
    }
}