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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;


public class ClassyNumbers {
	static long [][][]dp;
	static int inp[];
	static int n;
	static int k;
	static boolean f;
	static char [] a;
	public static long ans(int idx,int lessthan ,int c) {
		
		if(c==4)return 0;
		if(idx==a.length)return 1;
		if(dp[idx][lessthan][c]!=-1)return dp[idx][lessthan][c];
		long sum=0;
		if(lessthan==0)
		{
			for(int i=0;i<=a[idx]-'0';i++)
			{
				sum+=ans(idx+1,i==a[idx]-'0'?0:1,i==0?c:c+1);
			}
		}else {
			for(int i=0;i<=9;i++)
			{
				sum+=ans(idx+1,1,i==0?c:c+1);
			}
		}
		return dp[idx][lessthan][c]=sum;
	}
	
	public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        PrintWriter pw =new PrintWriter(System.out);
        int t=sc.nextInt();
        for(int i=0;i<t;i++) {
        	long l=sc.nextLong();
        	long r =sc.nextLong();
        	dp=new long [19][2][4];
        a=((l-1)+"").toCharArray();
        for(long x[][]:dp)
        {
        	for(long y[]:x)
        	Arrays.fill(y, -1);
        }
        long l1=ans(0,0,0);
        for(long x[][]:dp)
        {
        	for(long y[]:x)
        	Arrays.fill(y, -1);
        }
        a=(r+"").toCharArray();
        long l2=ans(0,0,0);
        pw.println(l2-l1);

        pw.flush();
	}
	}
	
	static class Scanner {
		 
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public Scanner(String file) throws Exception {
			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 String nextLine() throws IOException {
			return br.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 br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}

}