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 {
			public static boolean visited[]; 
			public static Integer distances[]; 
			public static Integer dp[][]; 
			
			static List<Long> s = new ArrayList<Long>(); 
			 public static long lower_bound(List<Long> numbers, long q) {
			        int l = -1;
			        int r = numbers.size();
			        int m;
			        while (r - l > 1) {
			            m = (l + r) / 2;
			            if (numbers.get(m) <= q) {
			                l = m;
			            } else {
			                r = m;
			            }
			        }
			 
			        return l;
			    }
			 
			    public static long upper_bound(List<Long> numbers, long q) {
			        int l = -1;
			        int r = numbers.size();
			        int m;
			        while (r - l > 1) {
			            m = (l + r) / 2;
			            if (numbers.get(m) >= q) {
			                r = m;
			            } else {
			                l = m;
			            }
			        }
			 
			        return r;
			    }
			 
			public static void brute (int pos , int count , long value) {
				if(pos==18) {
					s.add(value); 
					return ; 
				}
				brute(pos+1,count,value*10); 
				if(count<3) {
				for(int i = 1 ; i <=9 ; i++) {
					brute(pos+1,count+1,value*10+i);
				}
				
			}
			}
			
		    public static void main ( String args[] ) {
		    	FastReader sc = new FastReader();
		    	int t = sc.nextInt(); 
		    	brute(0,0,0); 
	    		s.add((long)1e18);
		    	while(t-->0) {
		    		long l = sc.nextLong(); 
		    		long r = sc.nextLong();
		            System.out.println(lower_bound(s, r) - upper_bound(s, l) + 1L);

		    	}
		    	
		    	
		   	
		    }
				
		     static class Graph
		    {
		        public int V;  
		        public LinkedList<Integer> adj[];
 		        Graph(int v)
		        {
		            V = v;
		            visited = new boolean[v+1]; 
		            distances = new Integer[v+1]; 
		            for(int i = 0 ; i <v+1 ; i++)
		            	distances[i] = -1  ;
		            adj = new LinkedList[v+1];
		            for (int i=0; i<v+1; ++i)
		                adj[i] = new LinkedList<Integer>();
		        }
		        void addEdge(int v, int w)
		        {
		            adj[v].add(w); 
		        }
		        void dfs(int node) {
		        	visited[node]= true; 
		        	System.out.print(node+" ");
		        	for(int x :adj[node]) {
		        		if(!visited[x])
		        			dfs(x); 
		        	}
		        	
		        }
		        void bfs(int node){
		            Queue<Integer> q = new LinkedList<Integer>();   ;
		            distances[node]= 0 ;
		            q.add(node);
		            while(!q.isEmpty()){
		                int src = q.peek();
		                System.out.print(src+" ");
		                q.remove();
		                int cost = distances[src];
		                for(int child : adj[src]){
		                    if(distances[child]==-1){
		                        q.add(child);
		                        distances[child]= cost+1;
		                    }
		                }
		            }
		        }
		        public  int graph_height(int node) {
		        	int h = 0 ; 
		        	for(int x : adj[node])
		        		h= Math.max(h,1+graph_height(x));
		  
		        return h ; 
		          
		    }
		    }
		     
		    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;
				}
		}
		 }
		  class Pair {
			int x ;
			int y ;
			public Pair(int x ,int y){
				this.x = x;
				this.y=y;}
		}
 
		  class Pair1 implements Comparable{
			int x ;
			int y ;
			public Pair1(int x ,int y){
				this.x = x;
				this.y=y;}
			public int compareTo(Object o) {
				Pair1 a = (Pair1) o ;
 
				return (this.x-a.x);
			}
 
			}
		 class Pair2 implements Comparable{
			int x ;
			int y ;
			public Pair2(int x ,int y){
				this.x = x;
				this.y=y;}
			public int compareTo(Object o) {
				Pair2 a = (Pair2) o ;
 
				return (this.y-a.y);
			}
		 }