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 Main
{
	static ArrayList<Long> list = new ArrayList<Long>(); 

	public static void main(String[] args)
	{
		FastReader reader = new FastReader();
		PrintWriter writer = new PrintWriter(System.out);

		add(0, 0, 0);
		list.add(1000000000000000000L);

		int t = reader.nextInt();
		while (t > 0)
		{
			int l = lower(reader.nextLong());
			int r = upper(reader.nextLong());

			writer.println(r-l);
			t--;
		}

		writer.close();
	}

	static int lower(long x)
	{
		int start = 0;
		int end = list.size()-1;
		int ans = -1;

		while (start <= end)
		{
			int mid = (start+end)/2;

			if (list.get(mid) < x)
			{
				ans = mid;
				start = mid+1;
			}
			else
				end = mid-1;
		}

		return ans;
	}

	static int upper(long x)
	{
		int start = 0;
		int end = list.size()-1;
		int ans = -1;

		while (start <= end)
		{
			int mid = (start+end)/2;

			if (list.get(mid) <= x)
			{
				ans = mid;
				start = mid+1;
			}
			else
				end = mid-1;
		}

		return ans;
	}

	static void add(int digits, int length, long val)
	{
		if (length == 18)
			list.add(val);
		else
		{
			add(digits, length+1, val*10);

			if (digits < 3)
				for (int i=1; i<10; i++)
					add(digits+1, length+1, val*10+i);
		}
	}

	static class FastReader
	{
		BufferedReader br;
		StringTokenizer st;

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

		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());
		}

		long nextLong()
		{
			return Long.parseLong(next());
		}

		double nextDouble()
		{
			return Double.parseDouble(next());
		}

		String nextLine()
		{
			String str = "";
			try
			{
				str = br.readLine();
			}
			catch (IOException e)
			{
				e.printStackTrace();
			}
			return str;
		}
	}
}