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.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.TreeSet;

public class Recursive {
	String INPUT = "";

	public static void main(String[] args) throws Exception {
		new Recursive().run();
	}

	private void solve() {
		long arr[] = new long[30];
		String s = "9";
		for (int i = 1; i <= 18; i++) {
			arr[i] = Long.parseLong(s);
			s = s + "9";
		}
		TreeSet<Long> set = new TreeSet<Long>();
		long temp = 1;
		for (int k = 0; k <= 18; k++) {
			for (int i = 1; i <= 9; i++) {
				set.add(i * temp);
			}
			temp = temp * 10;
		}
		int T = nextInt();
		while (T-- > 0) {
			long number1 = nextLong() - 1;
			long answer1 = getNdigit(arr, set, number1, 1)
					+ getNdigit(arr, set, number1, 2)
					+ getNdigit(arr, set, number1, 3);

			long number2 = nextLong();
			long answer2 = getNdigit(arr, set, number2, 1)
					+ getNdigit(arr, set, number2, 2)
					+ getNdigit(arr, set, number2, 3);
			System.out.println(answer2 - answer1);
		}

	}

	public static Long dp[][] = new Long[20][5];// 9count's nonzerodigit

	public long getNdigit(long arr9[], TreeSet<Long> set1, long number,
			int nonZeroDigitRequired) {
		// System.out.println("Called For : " + number + " "
		// + nonZeroDigitRequired);
		if (nonZeroDigitRequired == 1) {
			return set1.headSet(number, true).size();
		} else if (nonZeroDigitRequired > 1) {
			int size = (number + "").length();
			if (size == 1) {
				if (nonZeroDigitRequired == 1) {
					return number;
				} else {
					return 0;
				}
			} else {
				long startZeroAns = 0;
				if (dp[size - 1][nonZeroDigitRequired] == null) {
					startZeroAns = getNdigit(arr9, set1, arr9[size - 1],
							nonZeroDigitRequired);
					dp[size - 1][nonZeroDigitRequired] = startZeroAns;
				} else {
					startZeroAns = dp[size - 1][nonZeroDigitRequired];
				}
				int startDigit = Integer
						.parseInt((number + "").substring(0, 1));
				long leftOverNumber = Long.parseLong((number + "").substring(1,
						size));
				long diffAns = 0;
				if (startDigit > 1) {
					long temp = 0;
					if (dp[size - 1][nonZeroDigitRequired - 1] == null) {
						temp = getNdigit(arr9, set1, arr9[size - 1],
								nonZeroDigitRequired - 1);
						dp[size - 1][nonZeroDigitRequired - 1] = temp;
					} else {
						temp = dp[size - 1][nonZeroDigitRequired - 1];
					}
					diffAns = (startDigit - 1) * temp;
				}
				long leftOverAns = 0;
				if (all9(leftOverNumber)) {
					int len = (leftOverNumber + "").length();
					if (dp[len][nonZeroDigitRequired - 1] == null) {
						leftOverAns = getNdigit(arr9, set1, leftOverNumber,
								nonZeroDigitRequired - 1);
						dp[len][nonZeroDigitRequired - 1] = leftOverAns;
					} else {
						leftOverAns = dp[len][nonZeroDigitRequired - 1];
					}
				} else {
					leftOverAns = getNdigit(arr9, set1, leftOverNumber,
							nonZeroDigitRequired - 1);
				}

				return startZeroAns + diffAns + leftOverAns;
			}
		} else {
			throw new RuntimeException("lol");
		}

		// 97
		// 0 (9) 2
		// 8*(9) 1
		// 7 1
		//

		//
		// 37890098
		// 09999999 (n)
		// 2*(9999999) (n-1)
		// 7890098 (n-1)

		// conditions :
	}

	private boolean all9(long leftOverNumber) {
		String str = leftOverNumber + "";
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) != '9') {
				return false;
			}
		}
		return true;
	}

	InputStream is;
	PrintWriter out;

	void run() throws Exception {
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nextDouble() {
		return Double.parseDouble(nextString());
	}

	private char nextCharactor() {
		return (char) skip();
	}

	private String nextString() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b !=
									// ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] nextString(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nextMap(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = nextString(m);
		return map;
	}

	private int[] nextIntArr(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	private int nextInt() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nextLong() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = true;// System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}