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.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Deque;
import java.io.ObjectInputStream.GetField;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TimeZone;
import java.util.TreeMap;
import java.text.*;

public class Main {
	static final int MAX = (int) 1e9;
	static ArrayList<Long>res=new ArrayList<Long>();
	public static void solve(int pos,int cnt,long num)
	{
		if(pos==18)
		{
			res.add(num);
			return;
		}
		solve(pos+1,cnt,num*10);
	
		for(int i=1;i<10;i++)
			if(cnt<3)
			solve(pos+1,cnt+1,num*10+i);
	}
	public static void main(String[] args) throws IOException {
		FastReader in = new FastReader();
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		solve(0,0,0);
		res.add((long)(1e18));
		int t=in.nextInt(),firstIdx = 0,secondIdx = 0,l,r,mid;
		long a , b;
		while(t-->0)
		{
			a=in.nextLong();
			b=in.nextLong();
			l=0;
			r=res.size()-1;
			while(l<=r)
			{
				mid=(l+r)/2;
				if(res.get(mid)>=a)
				{
					firstIdx=mid;
					r=mid-1;
				}
				else 
					l=mid+1;
			}
			
			l=0;
			r=res.size()-1;
			while(l<=r)
			{
				mid=(l+r)/2;
				if(res.get(mid)<=b)
				{
					secondIdx=mid;
					l=mid+1;
				}
				else 
					r=mid-1;
			}
			if(firstIdx>secondIdx)
				out.write(0+"\n");
			else 
				out.write((secondIdx-firstIdx+1)+"\n");
			
		}
		out.close();

	}

}

class FastReader {
	BufferedReader br;
	StringTokenizer st;

	public FastReader() {
		br = new BufferedReader(new InputStreamReader(System.in));

	}

	public FastReader(File f) throws FileNotFoundException {
		br = new BufferedReader(new FileReader(f));
	}

	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());

			} catch (IOException e) {
				e.printStackTrace();
			}

		}

		return st.nextToken();

	}

	int nextInt() {

		return Integer.parseInt(next());
	}

	double nextDouble() {

		return Double.parseDouble(next());
	}

	long nextLong() {

		return Long.parseLong(next());
	}

	String nextLine() {
		String str = "";
		try {
			str = br.readLine();

		} catch (IOException e) {

			e.printStackTrace();
		}
		return str;

	}

	boolean ready() throws IOException {
		return br.ready();
	}
}