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{
    public static void main(String args[])
    {
        FastReader input=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
        long fac[]=new long[19];
        fac[0]=1;
        for(int i=1;i<=18;i++)
        {
            fac[i]=fac[i-1]*(long)i;
        }
        int T=input.nextInt();
        while(T-->0)
        {
            long l=input.nextLong();
            long r=input.nextLong();
            long val1=0;
            val1=fun(l-1,fac);
            long val2=fun(r,fac);
            out.println(val2-val1);
        }
        out.close();
    }
    public static long fun(long l,long fac[])
    {
        String s=String.valueOf(l);
        int nz=0;
        long sum=0;
        for(int i=0;i<s.length();i++)
        {
            int v=s.charAt(i)-'0';
            for(int j=0;j<v;j++)
            {
                int nz1=nz;
                if(j!=0) nz1++;
                if(nz1<=3)
                {
                    int len=s.length()-1-i;
                    for(int k=0;k<=3-nz1;k++)
                    {
                        if(k<=len)
                        {
                            sum+=comb(len,k,fac)*(long)Math.pow(9,k);
                        }
                    }
                }
            }
            if(v!=0) nz++;
        }
        int c=0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)!='0')
            {
                c++;
            }
        }
        if(c<=3) sum++;
        return sum;
    }
    public static void fun1(long l,long r)
    {
        int count=0;
        for(long i=l;i<=r;i++)
        {
            String s=String.valueOf(i);
            int c=0;
            for(int j=0;j<s.length();j++)
            {
                if(s.charAt(j)!='0')
                {
                    c++;
                }
            }
            if(c<=3)
            {
                count++;
            }
        }
        System.out.println(count);
    }
    public static long comb(int a,int b,long fac[])
    {
        long val=fac[a]/(fac[a-b]*fac[b]);
        return val;
    }
    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());
        }
        long nextLong()
        {
            return Long.parseLong(next());
        }
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        String nextLine()
        {
            String str="";
            try
            {
                str=br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}