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 C {
	static long memo[][][];
	static char[] digits;

	static long dp(int pos, boolean less, int non_zeros) {
		
		if (non_zeros > 3)
			return 0;
		int check = less ? 1 : 0 ;
		
		if (pos == digits.length)
					return 1;
		
		
		if (memo[check][non_zeros][pos] != -1)
			return memo[check][non_zeros][pos];

		int LMT = less ? 9 : digits[pos] - '0';
		long ans = 0 ; 
		
		for (int i = 0 ; i <= LMT; i++) 
			ans += dp(pos + 1 , less | i < LMT  , non_zeros + (i == 0 ? 0 : 1));
			
		
		return memo[check][non_zeros][pos] = ans;

	}
	static boolean can(long a)
	{
		int ans = 0 ; 
		for( ; a > 0 ; a /= 10 )
			if(a % 10 != 0)
				ans ++ ; 
			
		return ans <= 3 ; 
			
		
	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int TC = sc.nextInt();

		while (TC-- > 0) {

			String L = sc.next(), R = sc.next();
			long a, b;
			
			digits = L.toCharArray();
			
			memo = new long[2][4][digits.length];
			
			for(int i = 0 ; i < 2 ; i++)
				for(int j = 0 ; j < 4 ; j++)
					Arrays.fill(memo[i][j],-1);
			
			a = dp(0, false, 0);
			digits = new char[R.length()];
			digits = R.toCharArray();
			
			memo = new long[2][4][digits.length];
			for(int i = 0 ; i < 2 ; i++)
				for(int j = 0 ; j < 4 ; j++)
					Arrays.fill(memo[i][j],-1);

			b = dp(0, false, 0);
			out.println(b - (a - (can(Long.parseLong(L)) ? 1 : 0)));
			
		}
		
		out.flush();
		out.close();
		

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() throws Exception {

			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());

			return st.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}
	}

}