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.FileInputStream;
// import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.round;
import static java.lang.Math.sqrt;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;
import static java.util.Collections.reverse;
import static java.util.Collections.reverseOrder;
import static java.util.Collections.sort;
import static java.util.Comparator.comparing;
import static java.util.Comparator.comparingInt;
import static java.util.Comparator.comparingLong;

public class Main {
    FastScanner in;
    PrintWriter out;

    private void solve() throws IOException {
        for (int t = in.nextInt(); t-- > 0; )
            out.println(-ans(in.nextLong() - 1) + ans(in.nextLong()));
    }

    private long ans(long r) {
        if (r < 1000)
            return r;

        long[] d = new long[19];
        for (int i = 0; i < d.length; i++)
            d[i] = i == 0 ? 1 : d[i - 1] * 10;

        int len = 1;
        while (len < d.length && d[len] <= r)
            len++;

        long ans = 999;
        for (int i = 3; i < len; i++) {
            if (i + 1 < len)
                ans += 9 + 81 * i + 729 * i * (i - 1) / 2;

            else {
                for (int j = 1; d[i] * j <= r && j < 10; j++) {
                    if (d[i] * (j + 1) <= r)
                        ans += 1 + 9 * i + 81 * i * (i - 1) / 2;

                    else {
                        ans++;

                        for (int k = i - 1; k >= 0; k--) {
                            for (int l = 1; d[i] * j + d[k] * l <= r && l < 10; l++) {
                                if (d[i] * j + d[k] * (l + 1) <= r)
                                    ans += 1 + 9 * k;

                                else {
                                    ans++;

                                    for (int m = k - 1; m >= 0; m--)
                                        for (int n = 1; d[i] * j + d[k] * l + d[m] * n <= r && n < 10; n++)
                                            ans++;
                                }
                            }
                        }
                    }
                }
            }
        }

        return ans;
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}