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.util.Map.Entry;
import java.io.*;
        public class uu {
        	static Long [][][] memo;
        	static char[]arr1,arr2;
        	public static void main(String[] args) throws IOException, InterruptedException {
        		Scanner sc =new Scanner(System.in);
        		PrintWriter pw =new PrintWriter(System.out);
        		int t=sc.nextInt();
        		while (t-->0) {
        			arr1=((sc.nextLong()-1)+"").toCharArray();
        			arr2=sc.next().toCharArray();
        			memo=new Long [arr1.length][4][2];
        			long first=dp(0, 0, 0, arr1);
        			memo=new Long [arr2.length][4][2];
        			long last=dp(0,0,0,arr2);
        			pw.println(last-first);
        		}
        		pw.close();
        	}
        	public static long dp(int index ,int numOfNonZeros ,int ok,char[]arr) {
        		if (index==arr.length)
        			return 1;
        		if (memo[index][numOfNonZeros][ok]!=null)
        			return memo[index][numOfNonZeros][ok];
        		long sum=0;
        		int end = ok==1?9:arr[index]-'0';
        		for (int i=0;i<=end;++i) {
        			int take =i==0?numOfNonZeros:numOfNonZeros+1;
        			if (take>3)
        				continue;
        			int y=0;
        			if (ok==1||i<end)
        				y=1;
        		sum+=dp(index+1, take, y, arr);
        		}
        		return memo[index][numOfNonZeros][ok]=sum;
        	}
            static int mod(int x,int y)
            {
                if(x<0)
                    x=x+(-x/y+1)*y;
                return x%y;
            }
    		static long gcd(long a, long b) 
    		{ 
    		    if (a == 0) 
    		        return b; 
    		    return gcd(b % a, a); 
    		}
			static class Scanner {
				StringTokenizer stringTokenizer;
				BufferedReader bfBufferedReader;
				public Scanner(InputStream system) {
					bfBufferedReader=new BufferedReader(new InputStreamReader( system));
				}
				 public Scanner(String file) throws Exception {
			            bfBufferedReader = new BufferedReader(new FileReader( file));
			        }			 
			        public String next() throws IOException {
			            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens())
			                stringTokenizer = new StringTokenizer( bfBufferedReader.readLine());
			            return stringTokenizer.nextToken();
			        }
			 
			        public String nextLine() throws IOException {
			            return bfBufferedReader.readLine();
			        }
			 
			        public int nextInt() throws IOException {
			            return Integer.parseInt(next());
			        }
			 
			        public double nextDouble() throws IOException {
			            return Double.parseDouble(next());
			        }
			 
			        public char nextChar() throws IOException {
			            return next().charAt(0);
			        }
			 
			        public Long nextLong() throws IOException {
			            return Long.parseLong(next());
			        }
			 
			        public boolean ready() throws IOException {
			            return bfBufferedReader.ready();
			        }
			 
			        public void waitForInput() throws InterruptedException {
			            Thread.sleep(3000);
			        }
			    }
        }