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 Classy_Number {
	static StringBuilder sb;
	static dsu dsu;
	static long fact[];
	static int mod = (int) (1e9 + 7);

	static void solve() {
		dp = new long[20][4][2];
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 4; j++) {
				long[] arr = dp[i][j];
				Arrays.fill(arr, -1);
			}
		}
		long l = l();
		long r = l();
		s = l - 1 + "";
		long ans1 = solver(0, 0, true);

		dp = new long[20][4][2];
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 4; j++) {
				long[] arr = dp[i][j];
				Arrays.fill(arr, -1);
			}
		}
		s = r + "";
		long ans2 = solver(0, 0, true);

		sb.append(ans2 - ans1 + "\n");
	}

	static long[][][] dp;
	static String s;

	static long solver(int pos, int cnt, boolean bound) {
		if (pos == s.length()) {
			return 1;
		}

		if (dp[pos][cnt][(bound == true) ? 1 : 0] != -1) {
			return dp[pos][cnt][(bound == true) ? 1 : 0];
		}

		int ans = 0;
		int maxdigit = -1;
		if (bound == true) {
			maxdigit = s.charAt(pos) - '0';
		} else {
			maxdigit = 9;
		}

		for (int i = 0; i <= maxdigit; i++) {
			int cntupd = cnt + (i > 0 ? 1 : 0);
			long temp = 0;
			if (cntupd <= 3) {
				temp = solver(pos + 1, cntupd, (bound & (i == (s.charAt(pos) - '0'))));
			}

			ans += temp;
		}

		dp[pos][cnt][(bound == true) ? 1 : 0] = ans;
		return ans;
	}

	public static void main(String[] args) {
		sb = new StringBuilder();
		int test = i();
		while (test-- > 0) {
			solve();
		}
		System.out.println(sb);

	}

	/*
	 * fact=new long[(int)1e6+10]; fact[0]=fact[1]=1; for(int i=2;i<fact.length;i++)
	 * { fact[i]=((long)(i%mod)1L(long)(fact[i-1]%mod))%mod; }
	 */
//**************NCR%P******************	 
	static long ncr(int n, int r) {
		if (r > n)
			return (long) 0;

		long res = fact[n] % mod;
		// System.out.println(res);
		res = ((long) (res % mod) * (long) (p(fact[r], mod - 2) % mod)) % mod;
		res = ((long) (res % mod) * (long) (p(fact[n - r], mod - 2) % mod)) % mod;
		// System.out.println(res);
		return res;

	}

	static long p(long x, long y)// POWER FXN //
	{
		if (y == 0)
			return 1;

		long res = 1;
		while (y > 0) {
			if (y % 2 == 1) {
				res = (res * x) % mod;
				y--;
			}

			x = (x * x) % mod;
			y = y / 2;

		}
		return res;
	}

//**************END******************

	// *************Disjoint set
	// union*********//
	static class dsu {
		int parent[];

		dsu(int n) {
			parent = new int[n];
			for (int i = 0; i < n; i++)
				parent[i] = -1;
		}

		int find(int a) {
			if (parent[a] < 0)
				return a;
			else {
				int x = find(parent[a]);
				parent[a] = x;
				return x;
			}
		}

		void merge(int a, int b) {
			a = find(a);
			b = find(b);
			if (a == b)
				return;
			parent[b] = a;
		}
	}

//**************PRIME FACTORIZE **********************************//
	static TreeMap<Integer, Integer> prime(long n) {
		TreeMap<Integer, Integer> h = new TreeMap<>();
		long num = n;
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (n % i == 0) {
				int nt = 0;
				while (n % i == 0) {
					n = n / i;
					nt++;
				}
				h.put(i, nt);
			}
		}
		if (n != 1)
			h.put((int) n, 1);
		return h;

	}

//****CLASS PAIR ************************************************
	static class Pair implements Comparable<Pair> {
		int x;
		long y;

		Pair(int x, long y) {
			this.x = x;
			this.y = y;
		}

		public int compareTo(Pair o) {
			return (int) (this.y - o.y);

		}

	}
//****CLASS PAIR **************************************************

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int Int() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String String() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next() {
			return String();
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}

	static class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void printLine(Object... objects) {
			print(objects);
			writer.println();
		}

		public void close() {
			writer.close();
		}

		public void flush() {
			writer.flush();
		}
	}

	static InputReader in = new InputReader(System.in);
	static OutputWriter out = new OutputWriter(System.out);

	public static long[] sort(long[] a2) {
		int n = a2.length;
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a2)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < l.size(); i++)
			a2[i] = l.get(i);
		return a2;
	}

	public static char[] sort(char[] a2) {
		int n = a2.length;
		ArrayList<Character> l = new ArrayList<>();
		for (char i : a2)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < l.size(); i++)
			a2[i] = l.get(i);
		return a2;
	}

	public static long pow(long x, long y) {
		long res = 1;
		while (y > 0) {
			if (y % 2 != 0) {
				res = (res * x);// % modulus;
				y--;

			}
			x = (x * x);// % modulus;
			y = y / 2;
		}
		return res;
	}

//GCD___+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	public static long gcd(long x, long y) {
		if (x == 0)
			return y;
		else
			return gcd(y % x, x);
	}
	// ******LOWEST COMMON MULTIPLE
	// *********************************************

	public static long lcm(long x, long y) {
		return (x * (y / gcd(x, y)));
	}

//INPUT PATTERN********************************************************
	public static int i() {
		return in.Int();
	}

	public static long l() {
		String s = in.String();
		return Long.parseLong(s);
	}

	public static String s() {
		return in.String();
	}

	public static int[] readArrayi(int n) {
		int A[] = new int[n];
		for (int i = 0; i < n; i++) {
			A[i] = i();
		}
		return A;
	}

	public static long[] readArray(long n) {
		long A[] = new long[(int) n];
		for (int i = 0; i < n; i++) {
			A[i] = l();
		}
		return A;
	}

}