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.*;
import java.math.BigInteger;
 
public class Main
{
	static final int mod=(int)1e9+7;
	static int[] digit;
	static int n;
	static long[][][] dp; 
	public static void main(String[] args) throws Exception
	{
		FastReader in=new FastReader();
		PrintWriter out=new PrintWriter(System.out);
		int test=in.nextInt();
		while(test-->0)
		{
			long l=in.nextLong()-1;
			long r=in.nextLong();
			long ans=solve(l,r);
			out.println(ans);
		}
		out.flush();
	}

	static long solve(long l,long r)
	{
		String s=Long.toString(r);
		n=s.length();
		digit=new int[n];
		dp=new long[n][n][2];
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				dp[i][j]=new long[]{-1,-1};

		for(int i=0;i<n;i++)
			digit[i]=s.charAt(i)-'0';

		long ansr=recur(0,0,1);

		s=Long.toString(l);
		n=s.length();
		digit=new int[n];
		dp=new long[n][n][2];
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				dp[i][j]=new long[]{-1,-1};

		for(int i=0;i<n;i++)
			digit[i]=s.charAt(i)-'0';

		long ansl=recur(0,0,1);

		return ansr-ansl;
	}

	static long recur(int ind,int cnt,int f)
	{
		if(ind==n)
		{
			if(cnt<=3)
				return 1;
			return 0;
		}

		if(dp[ind][cnt][f]!=-1) return dp[ind][cnt][f];

		long ans=0;

		int d=f==1?digit[ind]+1:10;

		if(0<digit[ind])
			ans+=recur(ind+1,cnt,0);
		else
			ans+=recur(ind+1,cnt,f);

		if(cnt<3)
		{
			for(int i=1;i<d;i++)
			{
				if(i<digit[ind])
					ans+=recur(ind+1,cnt+1,0);
				else
					ans+=recur(ind+1,cnt+1,f);
			}
		}

		dp[ind][cnt][f]=ans;

		return ans;
	}
}
 
class FastReader
{
	BufferedReader br;
	StringTokenizer st;
 
	public FastReader()
	{
	    br=new BufferedReader(new InputStreamReader(System.in));
	}
 
	public String next() throws IOException
	{
	    if(st==null || !st.hasMoreElements())
	    {
	        st=new StringTokenizer(br.readLine());
	    }
	    return st.nextToken();
	}
 
	public int nextInt() throws IOException
	{
	    return Integer.parseInt(next());
	}
 
	public long nextLong() throws IOException
	{
	    return Long.parseLong(next());
	}
}