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.*;

public class CF3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		ArrayList<Long> temp = new ArrayList<>();
		for(int i=0;i<10;i++)
			for(int j=0;j<10;j++)
				for(int k=0;k<10;k++)
				{
					long factp = 1;
					for(int p=0;p<=16;p++)
					{
						long factq = factp*10;
						for(int q=p+1;q<=17;q++)
						{
							long factr = factq*10;
							for(int r=q+1;r<=18;r++)
							{
								long num = factp*(long)i + factq*(long)j + factr*(long)k;
								temp.add(num);
								factr = factr*10;
							}
							factq = factq*10;
						}
						factp = factp*10;
					}
				}
		TreeSet<Long> set = new TreeSet<>();
		for(int i=0;i<temp.size();i++)
			set.add(temp.get(i));
		ArrayList<Long> al = new ArrayList<>();
		for(long e : set)
			al.add(e);
		int t = s.nextInt();
		while(t-->0)
		{
			long l = s.nextLong();
			long r = s.nextLong();
			long ans = upper_bound(al,r) - lower_bound(al,l);
			System.out.println(ans);
		}
	}
	
	static int upper_bound(ArrayList<Long> al, long val)
	{
		int ans = al.size();
		int s = 0, e = al.size()-1;
		while(s<=e)
		{
			int m = (s+e)/2;
			if(al.get(m)>val)
				ans = m;
			if(al.get(m)>val)
				e = m-1;
			else
				s = m+1;
		}
		return ans;
	}
	
	static int lower_bound(ArrayList<Long> al, long val)
	{
		int ans = al.size();
		int s = 0, e = al.size()-1;
		while(s<=e)
		{
			int m = (s+e)/2;
			if(al.get(m)>=val)
				ans = m;
			if(al.get(m)>=val)
				e = m-1;
			else
				s = m+1;
		}
		return ans;
	}
}