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


public class A {

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        new A();
    }
    A() throws IOException {
        Reader.init(System.in);
        solve();
    }



    void solve() throws IOException {
        int T = Reader.nextInt();
        for(int tt = 0; tt < T; tt++) {
            String L = (Reader.nextLong() - 1) + "";
            String R = Reader.next();
            System.out.println(count(R) - count(L));
        }

    }

    long count(String x){
        if(Long.parseLong(x) < 1110){return Long.parseLong(x);}
        int first = x.charAt(0) - '0';
        long ans = 0;

        if(first - 1 != 0) { ans += (first-1)*((c2(x.length() - 1))*9*9 + (x.length() - 1)*9 + 1); }

        ans += (c3(x.length() - 1)*(9*9*9) + c2(x.length() - 1)*9*9 + (x.length()-1)*9 + 1);

        int next = -1;
        for(int i = 1; i < x.length(); i++){ if((x.charAt(i) - '0') != 0){next = i; break;}}
        if(next == -1){return ans;}

        int val = x.charAt(next) - '0';

        if((x.length() - next - 1) > 0){
            if(val - 1 != 0) {
                ans += (val - 1) * ((x.length() - next - 1) * 9 + 1);
            }
        }
        else{ans += (val); return ans;}

        if(x.length() - next - 1 >= 2){ans += (c2(x.length() - next - 1)*9*9 + (x.length() - next - 1)*9 + 1);}
        else if(x.length() - next - 1 == 1){ans += 10;}
        else{ans += 1;}

        int len = x.length() - next - 1;
        for(int i = next + 1; i < x.length(); i++){ next = i; if((x.charAt(i) - '0') != 0){ans += x.charAt(i) - '0' + 1; len = 0;  break;}}
        for(int i = next +1; i < x.length(); i++){ ans += 9; }
        if(len > 0)ans++;
        return ans - 1;
    }

    long c3(long x){
        if(x < 3){return 0;}
        return (x*(x-1)*(x-2))/6;
    }

    long c2(long x){
        if(x < 2){return 0;}
        return (x*(x-1))/2;
    }




}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
    /** call this method to initialize reader for InputStream */

    static void init(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");

    }

    static String nextToken() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {

                tokenizer = new StringTokenizer(reader.readLine());

            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    static String next() throws IOException {

        while ( ! tokenizer.hasMoreTokens() ) {

            tokenizer = new StringTokenizer(

                    reader.readLine() );

        }
        return tokenizer.nextToken();

    }

    static int nextInt() throws IOException {

        return Integer.parseInt( next() );

    }

    static double nextDouble() throws IOException {

        return Double.parseDouble( next() );

    }

    static long nextLong() {

        return Long.parseLong(nextToken());
    }
}