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 Main {
	
	public static void main(String[] args) throws IOException,InterruptedException{
		Scanner sc=new Scanner(System.in);
		generate(0,0,0l);
		long[] dp=new long[arrl.size()+1];
		int p=0;
		for (long k : arrl) {
			dp[p++]=k;
		}
		dp[dp.length-1]=(long)1e18;
		int t=sc.nextInt();
		while(t-->0) {
			long n=sc.nextLong(),m=sc.nextLong();
			pw.println(lower(m,dp)-upper(n,dp)+1);
		}
		pw.close();
    }
	
	static int lower(long x,long[] arr) {
		int start=0,end=arr.length-1,ans=-1;
		while(start<=end) {
			int mid=(start+end)/2;
			if(arr[mid]>x) {
				end = mid - 1;
			}else {
				ans=mid;
				start = mid + 1;
			}
		}
		return ans;
	}
	static int upper(long x,long[] arr) {
		int start=0,end=arr.length-1,ans=-1;
		while(start<=end) {
			int mid=(start+end)/2;
			if(arr[mid]<x) {
				start = mid + 1;
			}else {
				ans=mid;
				end = mid - 1;
			}
		}
		return ans;
	}
	
	static ArrayList<Long> arrl=new ArrayList<>();
	static void generate(int pos,int c,long num) {
		if (pos==18) {
			arrl.add(num);
			return;
		}
		generate(pos+1,c,num*10);
		if (c<3) {
			for (int i = 1; i <= 9; i++) {
				generate(pos+1,c+1,num*10+i);
			}
		}
	}
	
	static PrintWriter pw=new PrintWriter(System.out);
	static class pair implements Comparable<pair> {
		int x;
		int y;
 
		public pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
 
		public String toString() {
			return x + " " + y;
		}
		public boolean equals(Object o) {
            if (o instanceof pair) {
                pair p = (pair)o;
                return p.x == x && p.y == y;
            }
            return false;
        }
        public int hashCode() {
            return new Double(x).hashCode() * 31 + new Double(y).hashCode();
        }
        public int compareTo(pair other) {
        	if(this.x==other.x) {
        		return Long.compare(this.y, other.y);
        	}
			return Long.compare(this.x, other.x);
		}
	}
	static class tuble implements Comparable<tuble> {
		int x;
		int y;
		int z;
 
		public tuble(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
		public String toString() {
			return x + " " + y + " " + z;
		}
 
		public int compareTo(tuble other) {
			if (this.x == other.x) {
				if(this.y==other.y) return this.z - other.z;
				else return this.y - other.y;
			} else {
				return this.x - other.x;
			}
		}
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return false;
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}
}