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 Codeforces1036C {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int nTest = scanner.nextInt();
		for(int iTest = 0; iTest < nTest; iTest++) {
			long l = scanner.nextLong();
			long r = scanner.nextLong();
			long ans = countClassy(r, 3) - countClassy(l - 1, 3);
			System.out.println(ans);
		}
	}

	private static long countClassy(long n, int maxNumNonZeros) {
		Map<CountInfoWrapper, Long> memo = new HashMap<>();
		return recursiveCountClassy(memo, Long.toString(n), maxNumNonZeros, 0, false, 0);
	}

	private static long recursiveCountClassy(Map<CountInfoWrapper, Long> memo, String strN, int maxNumNonZeros, int pos, boolean isSmaller, int numNonZeros) {
		if(pos == strN.length()) {
			return 1;
		}
		CountInfoWrapper info = new CountInfoWrapper(pos, isSmaller, numNonZeros);
		if(memo.containsKey(info)) {
			return memo.get(info);
		}
		long result = 0;
		for(int i = 0; i < 10; i++) {
			if(!isSmaller && i > Character.digit(strN.charAt(pos), 10)) {
				continue;
			}
			if(numNonZeros == maxNumNonZeros && i != 0) {
				continue;
			}
			int nextPos = pos + 1;
			boolean nextIsSmaller = isSmaller || i < Character.digit(strN.charAt(pos), 10);
			int nextNumNonZeros = numNonZeros;
			if(i != 0) {
				nextNumNonZeros++;
			}
			result += recursiveCountClassy(memo, strN, maxNumNonZeros, nextPos, nextIsSmaller, nextNumNonZeros);
		}
		memo.put(info, result);
		return result;
	}
}

class CountInfoWrapper {
	private int pos;
	private boolean isSmaller;
	private int numNonZeros;

	public CountInfoWrapper(int pos, boolean isSmaller, int numNonZeros) {
		this.pos = pos;
		this.isSmaller = isSmaller;
		this.numNonZeros = numNonZeros;
	}

	@Override
	public boolean equals(Object object) {
		CountInfoWrapper other = (CountInfoWrapper)object;
		return pos == other.pos && isSmaller == other.isSmaller && numNonZeros == other.numNonZeros;
	}

	@Override
	public int hashCode() {
		int result = pos;
		result = result * 31 + (isSmaller ? 1 : 0);
		result = result * 31 + numNonZeros;
		return result;
	}
}