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.math.BigInteger;
public class C1036{
public static long mod = 1000000007;
public static int dx[] = {-1,0,1,0,-1,-1,1,1,-1};//primero ady, despues esq
public static long dp[][];
public static int dy[] = {0,1,0,-1,1,1,-1,-1};
public static void main(String args[]) throws IOException{
StringBuilder sb = new StringBuilder("");
BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
//String tmp[] = lector.readLine().split(" ");
int cas = Integer.parseInt(lector.readLine());
dp = new long[20][4];
for(int n = 0;n<dp.length;n++){
for(int k = 0;k<4;k++){
for(int i = 1;i<=k;i++){
long bin = 1;
for(int r = 0;r<i;r++)bin*=(long)(n-r);
for(int r = 1;r<=i;r++)bin/=(long)r;
dp[n][k]+=Math.pow(9,i)*bin;
}
dp[n][k]+=1;
}
}
//for(int n = 0;n<20;n++)
//System.out.println(dp[n][1]+" "+dp[n][2]+" "+dp[n][3]);//hag(String.valueOf(Math.pow(10,n)),0));

for(int n = 0;n<cas;n++){
String tmp[] = lector.readLine().split(" ");
long res = tmp[0].compareTo("0")==0?hag(tmp[1],0):hag(tmp[1],0)-hag(String.valueOf(Long.parseLong(tmp[0])-1),0);
sb.append(res+"\n");
}
System.out.print(sb);
}
public static long hag(String a,int b){
if(b>3)return 0;
if(a.length()==0)return 1;
//if(a.compareTo("0")==0)return b==0?0:b<3?1:0;
int aa = a.charAt(0)-'0';
if(aa==0) return hag(a.substring(1,a.length()),b);

long hpta = dp[a.length()-1][Math.min(3-b,a.length()-1)]+
(aa-1)*(3-b-1<0?0:dp[a.length()-1][Math.min(3-b-1,a.length()-1)])+hag(a.substring(1,a.length()),b+1);
//System.out.println(a+" "+b);
return hpta;
}
}
class p implements Comparable{
public int a;
public p(int a){
this.a = a;
}
public String toString(){
return "";
}
public int compareTo(Object o){
p pp = (p)o;
return (int)Math.signum(a-pp.a);
}
}
//sergio1