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 Main {
   static class pair implements Comparable<pair>{
        int a;
        int b;
        public pair(int a, int b){
            this.a=a;
            this.b=b;
        }
        public int compareTo(pair p){
            return (a-p.a==0)?Integer.compare(b,p.b):a-p.a;
        }
          
   }
  public static void main(String[] args) throws IOException,InterruptedException{
	BufferedReader	 br = new BufferedReader(new InputStreamReader(System.in));
	PrintWriter out = new PrintWriter(System.out);
     	// String s = br.readLine();
        // char[] arr=s.toCharArray();
        // ArrayList<Integer> arrl = new ArrayList<Integer>(); 
        // TreeSet<Integer> ts1 = new TreeSet<Integer>(); 
        // HashSet<Integer> h = new HashSet<Integer>(); 
        // HashMap<Integer, Integer> map= new HashMap<>(); 
        // PriorityQueue<String> pQueue = new PriorityQueue<String>(); 
        // LinkedList<String> object = new LinkedList<String>(); 
        // StringBuilder str = new StringBuilder();
        
        //*******************************************************//
 	   //  StringTokenizer   st = new StringTokenizer(br.readLine());
 	   // 	  int t = Integer.parseInt(st.nextToken());
 	   //    while(t-->0){
 	   //        st = new StringTokenizer(br.readLine());
 	   // 	  int n = Integer.parseInt(st.nextToken());
 	   // 	  int[] arr = new int[n];
 	   // 	  st = new StringTokenizer(br.readLine());
 	   // 	  for(int i=0; i<n; i++){
 	   // 	      arr[i] =Integer.parseInt(st.nextToken());
 	   // 	  }
 	   // 	  int ans =0;
 	   // 	  out.println(ans);
 	   //    }
 	          StringTokenizer   st = new StringTokenizer(br.readLine());
 	    	  int t = Integer.parseInt(st.nextToken());
 	       while(t-->0){
 	           st = new StringTokenizer(br.readLine());
 	           String a = st.nextToken();String b = st.nextToken();
 	           n = b.length();
 	            arr = new int[n];
 	            arr2 = new int[n];
 	           int x = a.length()-1;
 	           for(int i = n-1; i>=0; i--){
 	               if(x>=0)arr[i] = a.charAt(x)-'0';
 	               else arr[i]=0;
 	               arr2[i] = b.charAt(i)-'0';
 	               x--;
 	           }
 	           dp = new long[n][n][2][2];
 	           for(int i=0; i<n; i++)for(int k =0; k<n; k++){ Arrays.fill(dp[i][k][0],-1);Arrays.fill(dp[i][k][1],-1);}
 	           long ans = solve(0,0,0,0);
 	           out.println(ans);
 	       }
              out.flush();
 	    	  }
 	    	  static int n;
 	    	  static int[] arr;
 	    	  static int[] arr2;
              static long[][][][]dp;
              public static long solve(int i, int sum, int b,int s){
                  if(sum>3) return 0l;
                  if(i>=n) return 1l;
                  if(dp[i][sum][b][s]!=-1) return dp[i][sum][b][s];
                  long tmp = 0l;
                  int start =0;
                  int end =0;
                  if(b==0){
                      start =arr[i];
                  }else start = 0;
                  if(s==0){
                      end = arr2[i];
                  }else end = 9;
                  for(int idx=start; idx<=end; idx++){
                      tmp+= solve(i+1,(idx==0)?sum:sum+1,idx>arr[i]?1:b,idx<arr2[i]?1:s);
                  }
                  return dp[i][sum][b][s]=tmp;
              }
	}