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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Contest {
	private static PrintWriter out = new PrintWriter(System.out);
	private static int n, m, k, tc;
	private static int[] a;
	private static int[][] grid;
	private static ArrayList<Long> res = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		brute(0, 0, 0);
		Collections.sort(res);
		res.add(1000000000000000000L);
		tc = sc.nextInt();
		while(tc-->0) {
			long l = sc.nextLong(), r = sc.nextLong();
			
			out.println((lb(r) - lb(l - 1)));
		}
		out.flush();
	}
	
	private static void brute(int count, int pos, long num) {
		// base case
		if(pos == 18) {
			res.add(num);
			return;
		}
		// zero
		brute(count, pos + 1, num * 10);
		if(count < 3) {
			for(int i = 1;i <= 9;i++) {
				brute(count + 1, pos + 1, num*10 + i);
			}
		}
	}
	
	
	private static int lb(long x) {
		int ans = 0;
		int l = 0, r = res.size() - 1;
		while(l <= r) {
			int mid = l + (r - l) / 2;
			if(res.get(mid) <= x) {
				ans = mid;
				l = mid + 1;
			}else {
				r = mid - 1;
			}
		}
		return ans;
	}
	

	private static int solve(int x) {
		int count = 0;
		for (int i = 0; i <= x; i++) {
			if (solveHelper(i)) {
				System.out.println(i);
				count++;
			}
		}
		return count;
	}
	
	private static int tuple(int n) {
		int count = 0;
		for(int i = 0;i < n;i++)
			for(int j = i + 1;j < n;j++)
				for(int k = j + 1;k < n;k++) {
					System.out.println(i + " " + j + " " + k);
					count++;
				}
		return count;
	}

	private static boolean solveHelper(int x) {
		boolean[] vis = new boolean[10];

		int d = 3;
		while (x != 0) {
			int b = x % 10;
			if (!vis[b]) {
				if (d == 0)
					return false;
				vis[b] = true;
				d--;
			}
			x /= 10;
		}
		return true;

	}

	static final Random random = new Random();

	static void ruffleSort(int[] a) {
		int n = a.length;// shuffle, then sort
		for (int i = 0; i < n; i++) {
			int oi = random.nextInt(n), temp = a[oi];
			a[oi] = a[i];
			a[i] = temp;
		}
		java.util.Arrays.sort(a);
	}

//	private static class Scanner {
//		public BufferedReader reader;
//		public StringTokenizer st;
//
//		public Scanner(InputStream stream) {
//			reader = new BufferedReader(new InputStreamReader(stream));
//			st = null;
//		}
//
//		public String next() {
//			while (st == null || !st.hasMoreTokens()) {
//				try {
//					String line = reader.readLine();
//					if (line == null)
//						return null;
//					st = new StringTokenizer(line);
//				} catch (Exception e) {
//					throw (new RuntimeException());
//				}
//			}
//			return st.nextToken();
//		}
//
//		public int nextInt() {
//			return Integer.parseInt(next());
//		}
//
//		public long nextLong() {
//			return Long.parseLong(next());
//		}
//
//		public double nextDouble() {
//			return Double.parseDouble(next());
//		}
//	}

}