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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main
{
	static String l;
	static String r;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int t = Integer.parseInt(br.readLine());
		while(t-->0)
		{
			String[] inp = br.readLine().split(" ");
			l = inp[0]; r = inp[1];
			long R = dp(0,0,r,true);
			long L = dp(0,0,l,true);
			long ans = R-L;
			int c=0;
			for(int i=0;i<l.length();i++)
				if(l.charAt(i)!='0')c++;
			if(c<=3)ans++;
			pw.println(ans);
			
		}
		pw.close();
	}
	
	static long dp(int bit, int cur, String max, boolean left)
	{
		if (bit == max.length()) return 1;
		if(cur == 3) return dp(bit+1,3,max,false);
		if (left)
		{
			long ans=0;
			if(max.charAt(bit)>='2')
			{
				ans+=(Integer.parseInt(max.charAt(bit)+"")-1) * dp(bit+1,cur+1,max,false);
			}
			if(max.charAt(bit)>='1') ans += dp(bit+1,cur+1,max,true) + dp(bit+1,cur,max,false);
			if(max.charAt(bit)=='0') ans+=dp(bit+1,cur,max,true);
			return ans;
		}
		return dp(bit+1,cur,max,false) + 9*dp(bit+1,cur+1,max,false);
		
	}

}