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.math.*;
import java.util.*;

import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;

public class C {
	static int mod = 1000000007;
	static InputReader in = new InputReader(System.in);
	static PrintWriter out = new PrintWriter(System.out);

	static String s1,s2;
	static long[][][] dp1,dp2;
	
	static long func1(int idx,int count,int small)
	{
		if(idx>=s1.length())
		{
			//tr("ret");
				return 1;
		}
		if(dp1[idx][count][small]!=-1)
		{
			return dp1[idx][count][small];
		}
		long ret=0;
		if(small==0)
		{
			int curidx=s1.charAt(idx)-'0';
			if(curidx==0)
				ret+=func1(idx+1, count, small);
			else
			{
				if(count+1<=3)
					ret+=func1(idx+1, count+1, small);
			}
			for(int i=curidx-1;i>=0;i--)
			{
				if(i!=0)
				{
					if(count+1<=3)
					{
						ret+=func1(idx+1, count+1, 1);
					}
				}
				else
				{
					ret+=func1(idx+1, count, 1);
				}
			}
		}
		else
		{
			for(int i=0;i<=9;i++)
			{
				if(i!=0)
				{
					if(count+1<=3)
					{
						ret+=func1(idx+1, count+1, 1);
					}
				}
				else
				{
					ret+=func1(idx+1, count, 1);
				}
			}
		}
		return dp1[idx][count][small]=ret;
	}
	
	static long func2(int idx,int count,int small)
	{
		if(idx>=s2.length())
		{
				return 1;
		}
		if(dp2[idx][count][small]!=-1)
		{
			return dp2[idx][count][small];
		}
		long ret=0;
		if(small==0)
		{
			int curidx=s2.charAt(idx)-'0';
			if(curidx==0)
				ret+=func2(idx+1, count, small);
			else
			{
				if(count+1<=3)
					ret+=func2(idx+1, count+1, small);
			}
			for(int i=curidx-1;i>=0;i--)
			{
				if(i!=0)
				{
					if(count+1<=3)
					{
						ret+=func2(idx+1, count+1, 1);
					}
				}
				else
				{
					ret+=func2(idx+1, count, 1);
				}
			}
		}
		else
		{
			for(int i=0;i<=9;i++)
			{
				if(i!=0)
				{
					if(count+1<=3)
					{
						ret+=func2(idx+1, count+1, 1);
					}
				}
				else
				{
					ret+=func2(idx+1, count, 1);
				}
			}
		}
		return dp2[idx][count][small]=ret;
	}
	
	public static void main(String[] args) {

		int tc=in.nextInt();
		while(tc-->0)
		{
			 s1=(in.nextLong()-1)+"";
			 s2=in.readString();
			 dp1=new long[20][4][2];
			 dp2=new long[20][4][2];
			 for(int i=0;i<20;i++)
			 {
				 for(int j=0;j<4;j++)
				 {
					 for(int k=0;k<2;k++)
					 {
						 dp1[i][j][k]=-1;
						 dp2[i][j][k]=-1;
					 }
				 }
			 }
			 long ans1=func1(0, 0, 0);
			 long ans2=func2(0, 0, 0);
			 long ans=ans2-ans1;
			 out.println(ans);
			 
		}
		out.close();

	}

	static class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;

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

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

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String readString() {
			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 String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

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

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
	}

	private static void tr(Object... o) {
		if (!(System.getProperty("ONLINE_JUDGE") != null))
			System.out.println(Arrays.deepToString(o));
	}
}