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.*;
import java.awt.Point;
import java.math.BigInteger;

public class classy {

	public static void main(String[] args) throws Exception {
		FastIO sc = new FastIO(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int T = sc.nextInt();
		
		for(int i = 0; i < T; i++) {
			String left = sc.next();
			dp = new long[2][3][left.length()];
			limit = new int[left.length()];
			for(int j = 0; j < left.length(); j++) {
				limit[j] = Character.digit(left.charAt(j), 10);
			}
			
			long leftCount = count();
			if(limit.length > 1) leftCount += countLimitless(limit.length-1);
			if(numNonZero(limit) <= 3) leftCount--;
			
			String right = sc.next();
			dp = new long[2][3][right.length()];
			limit = new int[right.length()];
			for(int j = 0; j < right.length(); j++) {
				limit[j] = Character.digit(right.charAt(j), 10);
			}
			
			long rightCount = count();
			if(limit.length > 1) rightCount += countLimitless(limit.length-1);
			pw.println(rightCount - leftCount);
		}
		
		pw.close();
	}
	
	static int numNonZero(int[] array) {
		int count = 0;
		for(int a : array) if(a != 0) count++;
		return count;
	}
	
	static long countLimitless(int length) {
		long dp[][] = new long[3][length];
		
		dp[0][0] = 9;
		for(int len = 0; len < length-1; len++) {
			for(int digs = 0; digs < 3; digs++) {
				if(digs < 2) {
					dp[digs+1][len+1] += 9*dp[digs][len];
				}
				dp[digs][len+1] += dp[digs][len];
			}
		}
		
		long ret = 0;
		for(int digs = 0; digs < 3; digs++) {
			for(int len = 0; len < length; len++) {
				ret += dp[digs][len];
			}
		}
		
		return ret;
		
	}
	
	static long count() {
		dp[0][0][0] = limit[0]-1;
		dp[1][0][0]++;
		
		for(int len = 0; len < limit.length-1; len++) {
			for(int digs = 0; digs < 3; digs++) {
				for(int next = 0; next < 10; next++) {
					if(next != 0) {
						if(digs < 2) {
							if(next == limit[len+1]) dp[1][digs+1][len+1] += dp[1][digs][len];
							if(next < limit[len+1]) dp[0][digs+1][len+1] += dp[1][digs][len];
							dp[0][digs+1][len+1] += dp[0][digs][len];
						}
					} else {
						if(next == limit[len+1]) dp[1][digs][len+1] += dp[1][digs][len];
						if(next < limit[len+1]) dp[0][digs][len+1] += dp[1][digs][len];
						dp[0][digs][len+1] += dp[0][digs][len];
					}
				}
			}
		}
		
		long total = 0;
		for(int lim = 0; lim < 2; lim++) {
			for(int digits = 0; digits < 3; digits++) {
				total += dp[lim][digits][limit.length-1];
			}
		}
		
		return total;
	}
	
	static int limit[];
	static long[][][] dp;
	
	static class FastIO {

		//Is your Fast I/O being bad?

		InputStream dis;
		byte[] buffer = new byte[1 << 17];
		int pointer = 0;

		public FastIO(String fileName) throws Exception {
			dis = new FileInputStream(fileName);
		}

		public FastIO(InputStream is) throws Exception {
			dis = is;
		}

		int nextInt() throws Exception {
			int ret = 0;

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}

			return (negative) ? -ret : ret;
		}

		long nextLong() throws Exception {
			long ret = 0;

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}

			return (negative) ? -ret : ret;
		}

		byte nextByte() throws Exception {
			if (pointer == buffer.length) {
				dis.read(buffer, 0, buffer.length);
				pointer = 0;
			}
			return buffer[pointer++];
		}

		String next() throws Exception {
			StringBuffer ret = new StringBuffer();

			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			while (b > ' ') {
				ret.appendCodePoint(b);
				b = nextByte();
			}

			return ret.toString();
		}

	}
}