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.*;

public class Task{
//  ..............code begins here..............

static long mod=(long)1e9+7,mod1=998244353l,inf=(long)1e18+5;
static long[][][] dp;
static List<Integer> l=new ArrayList<>();
static long rec(int p,int c,int f){
    if(c>3) return 0;
    if(p==l.size()){
        if(c<=3)return 1;
        return 0;
    }
    if(dp[p][c][f]!=-1) return dp[p][c][f];
    int lmt=f==1?l.get(p):9;
    long tmp=0;
    for(int i=0;i<=lmt;i++){
        int nf=0,nc=c;
        if(f==1&&i==lmt)nf=1;
        if(i>0)nc++;
        tmp+=rec(p+1,nc,nf);
    }
    return dp[p][c][f]=tmp;
}
static void solve() throws  IOException{
    long[] z=long_arr();
    long l1=z[0]-1,r=z[1];
    l.clear();
    while(r>0){
        l.add((int)(r%10));
        r/=10;
    }
    Collections.reverse(l);
    dp=new long[l.size()][4][2];
    for(int i=0;i<l.size();i++){
        for(int j=0;j<4;j++){
            dp[i][j][0]=dp[i][j][1]=-1;
        }
    }
    long res=rec(0,0,1);
    l.clear();
    while(l1>0){
        l.add((int)(l1%10));
        l1/=10;
    }
    Collections.reverse(l);
    dp=new long[l.size()][4][2];
    for(int i=0;i<l.size();i++){
        for(int j=0;j<4;j++){
            dp[i][j][0]=dp[i][j][1]=-1;
        }
    }
    res-=rec(0,0,1);
    out.write(res+"\n");

}


public static void main(String[] args) throws  IOException{
    assign();
    int t=int_v(read()),cn=1;
    while(t--!=0){
        //out.write("Case #"+cn+": ");
        solve();
        //cn++;
    }
    out.flush();
}

// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static void sort(int[] a){List<Integer> l=new ArrayList<>();for(int x:a){l.add(x);}Collections.sort(l);for(int i=0;i<a.length;i++){a[i]=l.get(i);}}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
//static String setpreciosion(double d,int k){BigDecimal d1 = new BigDecimal(Double.toString(d));return d1.setScale(k,RoundingMode.HALF_UP).toString();}//UP DOWN HALF_UP
static int add(int a,int b){int z=a+b;if(z>=mod)z-=mod;return z;}
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
static long Modpow(long a,long p,long m){long res=1;while(p>0){if((p&1)!=0){res=(res*a)%m;}p >>=1;a=(a*a)%m;}return res%m;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
//static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
//static long[] f;
}