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 int pos=0;
    static PrintWriter pw = new PrintWriter(System.out);
    static long[]arr=new long[607421];
	public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        solve(0,0,0);
        arr[607420]=1000000000000000000L;
        Sort(arr);
        int n=607421; 
       while(t-->0) {
        	long x=sc.nextLong();
        	long y=sc.nextLong();
        	int h=n-1;
        	int lo=0;
        	int res1=-1;
        	while(lo<=h){
        	    int mid=h+lo>>1;
        	    if(arr[mid]>=x){
        	        h=mid-1;
        	        res1=mid;
        	    }else lo=mid+1;
        	}
            h=n-1;
        	lo=0;
        	int res2=-1;
        	while(lo<=h){
        	    int mid=h+lo>>1;
        	    if(arr[mid]>y){
        	        h=mid-1;
        	    }else { lo=mid+1;res2=mid;}
        	}
            pw.println(res2-res1+1);
        }pw.close();
	}
	public static void solve(int ind,int count,long cur) {
		if(ind==18) {
			arr[pos++]=cur;
			return ;
		}
		solve(ind+1,count,cur*10);
		if(count<3)for(int i=1;i<=9;i++)solve(ind+1,count+1,cur*10+i);
	} 
    public static boolean prime(int x){
	    int[] arr=new int[10000000];
	    int index=0;
	    int num=3;
	    int i=0;
	    arr[0]=2;
	    while(num<=x){
	      for(i=0;i<=index;i++){
	          if(num%arr[i]==0){
	              break;
	          }
	      }
	      if(i==index+1){
	          arr[++index]=num;
	      }
	      num++;
	    }
	    if(arr[index]==x)return true;
	    return false;
	      
	}
    public static void conquer(long[] arr,int b,int m,int e){
	    int len1=m-b+1;
	    int len2=e-m;
	    long[] l=new long[len1];
	    long[] r=new long[len2];
	    for(int i=0;i<len1;i++){
	        l[i]=arr[b+i];
	    }
	   for(int j=0;j<len2;j++){
	            r[j]=arr[m+1+j];
	   }
	    int i=0,j=0,k=b;
	    while((i<len1)&&(j<len2)){
	        if(r[j]>=l[i]){
	            arr[k]=l[i];
	            k++;
	            i++;
	        }
	        else{
	           arr[k]=r[j];
	           k++;
	           j++;
	        }
	    }
	    while(i<len1){
	        arr[k++]=l[i++];
	    }
	    while(j<len2){
	        arr[k++]=r[j++];
	    }
	}
	static int mid;
	public static void sort(long[] arr,int b,int e){
	    if(b<e){
	        int mid =(e+b)/2;
	        sort(arr,b,mid);
	        sort(arr,mid+1,e);
	        conquer(arr,b,mid,e);
	    }
	}
    public static void Sort(long[] arr){
        sort(arr,0,arr.length-1);
    }
	static class Scanner {

		StringTokenizer st;

		BufferedReader br;



		public Scanner(InputStream s) {

			br = new BufferedReader(new InputStreamReader(s));

		}



		public Scanner(String file) throws FileNotFoundException {

			br = new BufferedReader(new FileReader(file));

		}



		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 boolean ready() throws IOException {

			return br.ready();

		}



	}

}