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

public class CFC {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    private static final long MOD = 1000L * 1000L * 1000L + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};
    private static final String yes = "Yes";
    private static final String no = "No";

    long[][] comb;
    int limit = 25;
    long[] pow9;
    void solve() throws IOException {
        comb = new long[limit][limit];
        for (int i = 0; i < limit; i++) {
            comb[i][i] = 1;
            comb[i][0] = 1;
        }

        pow9 = new long[10];
        pow9[0] = 1;
        for (int i = 1; i < pow9.length; i++) {
            pow9[i] = pow9[i - 1] * 9;
        }

        for (int i = 2; i < limit; i++) {
            for (int j = 1; j < limit; j++) {
                comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
            }
        }

        int t = nextInt();
        for (int p = 0; p < t; p++) {
            long l = nextLong();
            long r = nextLong();
            long res = helper(r);
            res -= helper(l - 1);

            outln(res);
        }
    }

    long helper(long bound) {
        if (bound <= 0) {
            return 0;
        }

        long res = 0;
        char[] arr = Long.toString(bound).toCharArray();
        int[] pref = new int[1 + arr.length];
        for (int i = 1; i <= arr.length; i++) {
            pref[i] = pref[i - 1] + (arr[i - 1] != '0' ? 1 : 0);
        }

        if (pref[arr.length] <= 3) {
            res++;
        }

        for (int i = 0; i < arr.length; i++) {
            int prefCnt = pref[i];
            for (char j = '0'; j < arr[i]; j++) {
                int has = prefCnt + 1;
                if (j == '0') {
                    has--;
                }

                int bits = arr.length - 1 - (i + 1) + 1;
                int left = 3 - has;
                for (int k = 0; k <= left; k++) {
                    if (bits >= k) {
                        res += comb[bits][k] * pow9[k];
                        if (i == 0 && j == '0' && k == 0) {
                            res--;
                        }
                    }
                }
            }
        }

        return res;
    }

    void shuffle(long[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            long tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    private void formatPrint(double val) {
        outln(String.format("%.9f%n", val));
    }
    public CFC() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFC();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}