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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.PrintWriter;
public class C1036 
{
    static class Scanner
    {
        BufferedReader br;
        StringTokenizer tk=new StringTokenizer("");
        public Scanner(InputStream is) 
        {
            br=new BufferedReader(new InputStreamReader(is));
        }
        public int nextInt() throws IOException
        {
            if(tk.hasMoreTokens())
                return Integer.parseInt(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextInt();
        }
        public long nextLong() throws IOException
        {
            if(tk.hasMoreTokens())
                return Long.parseLong(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextLong();
        }
        public String next() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return next();
        }
        public String nextLine() throws IOException
        {
            tk=new StringTokenizer("");
            return br.readLine();
        }
        public double nextDouble() throws IOException
        {
            if(tk.hasMoreTokens())
                return Double.parseDouble(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextDouble();
        }
        public char nextChar() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken().charAt(0));
            tk=new StringTokenizer(br.readLine());
            return nextChar();
        }
        public int[] nextIntArray(int n) throws IOException
        {
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArray(int n) throws IOException
        {
            long a[]=new long[n];
            for(int i=0;i<n;i++)
                a[i]=nextLong();
            return a;
        }
        public int[] nextIntArrayOneBased(int n) throws IOException
        {
            int a[]=new int[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArrayOneBased(int n) throws IOException
        {
            long a[]=new long[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextLong();
            return a;
        }
    
    
    }
    static long dp[][];
    static long sol(int i,char c[],int cnt,int e)
    {
        if(cnt<0)
            return 0;
        if(i==c.length)
            return 1;
        if(e==0)
            return dp[c.length-i][cnt];
        long cn=0;
        for(char x='0';x<='9';x++)
        {
            if(x>c[i])
                break;
            if(x<c[i])
            {
                if(x=='0')
                    cn+=sol(i+1,c,cnt,0);
                else
                    cn+=sol(i+1,c,cnt-1,0);
            }
            else if(x==c[i])
            {
                if(x=='0')
                    cn+=sol(i+1,c,cnt,1);
                else
                    cn+=sol(i+1,c,cnt-1,1);
                    
            }
        }
        return cn;
    }
    public static void main(String args[]) throws IOException
    {
        Scanner in=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int t=in.nextInt();
        dp=new long[20][4];
        for(int i=0;i<4;i++)
            dp[0][i]=1;
        for(int i=1;i<=19;i++)
        {
            dp[i][0]=1;
            dp[i][1]=i*10-(i-1);
            dp[i][2]=81*(i*(i-1))/2+dp[i][1];
            dp[i][3]=729*(i*(i-1)*(i-2))/6+dp[i][2];
            
        }
        while(t--!=0)
        {
            long l=in.nextLong();
            long r=in.nextLong();
            if(l==1)
                out.println(sol(0,Long.toString(r).toCharArray(),3,1)-1);
            else
                out.println(sol(0,Long.toString(r).toCharArray(),3,1)-sol(0,Long.toString(l-1).toCharArray(),3,1));
                
        }
        out.close();
    }

}