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.awt.Point;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.math.BigInteger;

public class ClassyNumbers {
    static class Solver {
        List<Long> list;

        public void solve(MyReader in, PrintWriter out) {
            list = new ArrayList<>();
            preCalc();
            int t = in.nextInt();
            while (t-- > 0) {
                long l = in.nextLong();
                long r = in.nextLong();

                int left = Collections.binarySearch(list, l);
//                if(left == -1)left = 0;
                if(left < 0)left = -(left)-1;
                int right = Collections.binarySearch(list, r);
                if(right<0)right = -right-2;



                out.println(right - left+1);
            }
        }


        void preCalc() {
            Queue<List<Long>> q = new ArrayDeque<>();
            list.add(0L);
            for (long i = 1; i <= 9; i++) q.add(Arrays.asList(i, 1L, 1L));

            while (!q.isEmpty()) {
                var cur = q.poll();
                long num = cur.get(0);
                long cnt = cur.get(1);
                long pos = cur.get(2);


                list.add(num);
                if (pos == 19) continue;
                q.add(Arrays.asList(num * 10, cnt, pos + 1));
                if (cnt < 3)
                    for (int i = 1; i <= 9; i++) {
                        q.add(Arrays.asList(num * 10 + i, cnt + 1, pos + 1));
                    }

            }


        }


    }

    public static void main(String[] args) {
        MyReader mr = new MyReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        new Solver().solve(mr, out);
        out.close();
    }

    //    static int[][] dir = {{0,1}, {1,0},{-1,0}, {0,-1}};
//    static int[][] dir = {{0,1}, {1,0},{-1,0}, {0,-1}, {-1,-1},{-1,1}, {1,1}, {1,-1}};
    static class MyReader {
        BufferedReader br;
        StringTokenizer st;

        MyReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String res = "";
            try {
                res = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return res;
        }

        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }

            return arr;
        }

        Integer[] nextIntegerArray(int n) {
            Integer[] arr = new Integer[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }

            return arr;
        }

        Long[] nextLongArray(int n) {
            Long[] arr = new Long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }

            return arr;
        }

        String[] nextStringArray(int n) {
            String[] arr = new String[n];
            for (int i = 0; i < n; i++) {
                arr[i] = next();
            }
            return arr;
        }
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}