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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ClassyNumbers solver = new ClassyNumbers();
        solver.solve(1, in, out);
        out.close();
    }

    static class ClassyNumbers {
        long[][][] memo = new long[19][4][2];

        long dp(List<Integer> s, int idx, int limit, int less) {
            if (limit == 0) {
                return 1;
            }
            if (idx == -1) {
                return 1;
            }
            if (memo[idx][limit][less] != -1) {
                return memo[idx][limit][less];
            }

            long ret = 0;
            if (less == 1) {
                // we can pick anything 0-9

                // Pick 0
                ret += dp(s, idx - 1, limit, less);

                for (int i = 1; i <= 9; i++) {
                    ret += dp(s, idx - 1, limit - 1, less);
                }
            } else {
                // we can pick anything 0-s[idx]

                // Pick 0
                ret += dp(s, idx - 1, limit, (s.get(idx) > 0) ? 1 : 0);

                for (int i = 1; i <= s.get(idx); i++) {
                    ret += dp(s, idx - 1, limit - 1, (i < s.get(idx)) ? 1 : 0);
                }
            }

            memo[idx][limit][less] = ret;
            return ret;
        }

        long f(long n) {
            List<Integer> s = new ArrayList<>();
            while (n > 0) {
                s.add((int) (n % 10));
                n /= 10;
            }

            for (long[][] x : memo) {
                for (long[] y : x) {
                    Arrays.fill(y, -1);
                }
            }
            return dp(s, s.size() - 1, 3, 0);
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int tt = in.ni();
            while (tt-- > 0) {
                solve(in, out);
            }
        }

        void solve(InputReader in, PrintWriter out) {
            long l = in.nl();
            long r = in.nl();

            long ans = f(r) - f(l - 1);
            out.println(ans);
        }

    }

    static class InputReader {
        private final InputStream is;
        private final byte[] inbuf = new byte[1024];
        private int lenbuf = 0;
        private int ptrbuf = 0;

        public InputReader(InputStream stream) {
            is = stream;
        }

        private int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public int ni() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nl() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

    }
}