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.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int t = sc.nextInt();
		for (int p = 0; p < t; p++) {
			long l = sc.nextLong();
			long r = sc.nextLong();

			num = getDigit(r);
			N = num.length;
			dp = new int[N + 1][4][2];
			for (int i = 0; i < N + 1; i++) {
				for (int j = 0; j < 4; j++) {
					for (int k = 0; k < 2; k++) {
						dp[i][j][k] = -1;
					}
				}
			}
			int resr = dp(0, 3, true);
			num = getDigit(l - 1);
			N = num.length;
			dp = new int[N + 1][4][2];
			for (int i = 0; i < N + 1; i++) {
				for (int j = 0; j < 4; j++) {
					for (int k = 0; k < 2; k++) {
						dp[i][j][k] = -1;
					}
				}
			}
			int resl = dp(0, 3, true);
			pw.println(resr - resl);
		}
		pw.close();
	}

	static int getNumber(long num) {
		int i = 0;
		while (num != 0) {
			num /= 10;
			i++;
		}
		return i;
	}

	static int[] getDigit(long num) {
		int n = getNumber(num);
		int[] arr = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			arr[i] = (int) (num % 10);
			num /= 10;
		}
		return arr;
	}

	static int[] num;
	static int N;
	static int[][][] dp;

	static int dp(int idx, int k, boolean lim) {
		if (idx == N && k >= 0)
			return 1;
		if (idx == N || k < 0)
			return 0;

		if (dp[idx][k][lim ? 1 : 0] != -1)
			return dp[idx][k][lim ? 1 : 0];
		int res = 0;
		int l = lim ? num[idx] : 9;
		for (int i = 0; i <= l; i++) {
			res += dp(idx + 1, i != 0 ? k - 1 : k, i == num[idx] ? lim : false);

		}
		return dp[idx][k][lim ? 1 : 0] = res;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				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());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		public int[] nextIntArr(int n) throws IOException {
			int arr[] = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		public int[] nextIntArr(int n, int f) throws IOException {
			int arr[] = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = f;
			}
			return arr;
		}

		public int[][] nextInt2DArr(int n, int m) throws IOException {
			int arr[][] = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int k = 0; k < m; k++) {
					arr[i][k] = nextInt();
				}
			}
			return arr;
		}

		public int[][] nextInt2DArr(int n, int m, int f) throws IOException {
			int arr[][] = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int k = 0; k < m; k++) {
					arr[i][k] = f;
				}
			}
			return arr;
		}

		public String[] nextStringArr(int n) throws IOException {
			String arr[] = new String[n];
			for (int i = 0; i < n; i++) {
				arr[i] = next();
			}
			return arr;
		}

		public char[] nextCharArr(int n) throws IOException {
			char arr[] = new char[n];
			for (int i = 0; i < n; i++) {
				arr[i] = next().charAt(0);
			}
			return arr;
		}

	}

	public static int max(int a, int b) {
		return a > b ? a : b;
	}

	public static int min(int a, int b) {
		return a < b ? a : b;
	}
}