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.*;
import java.io.*;
public class A
{
      static int n=0;
      static int a[];
      static long C[][]=new long[19][4];
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int t=Integer.parseInt(br.readLine());
            for(int u=0;u<t;u++)
            {
                  String s1[]=br.readLine().split(" ");
                  long l=Long.parseLong(s1[0])-1;
                  long r=Long.parseLong(s1[1]);
                  
                  for(int i=0;i<19;i++)
                   C[i][0]=1;
                  for(int i=0;i<19;i++)
                   C[i][1]=i;
                  
                  for(int i=2;i<19;i++)
                   C[i][2]=(i*(i-1))/2;
                  
                  for(int i=3;i<19;i++)
                   C[i][3]=(i*(i-1)*(i-2))/6;
                  System.out.println(find(r)-find(l));
            }
      }
      
      public static long get(int i,int x)
      {
            if(x<0)
             return 0;
            if(i==n)
             return 1;
            long S=0;
            
            if(a[i]==0)
             return get(i+1,x);
            
            for(int j=1;j<=x;j++)
             S+=C[n-i-1][j-1]*pow(9,j-1);
            S=S*(a[i]-1);
            for(int j=0;j<=x;j++)
             S+=C[n-i-1][j]*pow(9,j);
            return S+get(i+1,x-1);
      }
      public static long find(long l)
      {
                  n=0;
                  long ll=l;
                  while(ll>0)
                  { n++; ll=ll/10; }
                  
                  ll=l;
                  a=new int[n];
                  for(int i=n-1;i>=0;i--)
                  { a[i]=(int)(ll%10); ll=ll/10; }
                  
                  return get(0,3);
      }
      
      public static long pow(long x,int n)
      {
            if(n<0)
             return 0;
            long r=1;
            while(n>0)
            {
                  if(n%2==1)
                   r=r*x;
                  x=x*x;
                  n=n/2;
            }
            return r;
      }
}