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 C {
    public List<Long> a = new ArrayList<>((int) 1e6);

    public void gen(long cur, int cnt, int len) {
        a.add(cur);
        if (len == 19)
            return;
        int i = 0;
        if (cur == 0)
            i++;
        for (; i < 10; i++) {
            int newCnt = cnt;
            if (i != 0)
                newCnt++;
            if (newCnt <= 3)
                gen(cur * 10 + i, newCnt, len + 1);
        }
    }

    public long query(long start, long end) {
        int l = -1;
        int r = a.size();
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (a.get(m) >= start)
                r = m;
            else
                l = m;
        }
        int L = r;
        l = -1;
        r = a.size();
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (a.get(m) <= end)
                l = m;
            else
                r = m;
        }
        int R = l;
        if (R >= L)
            return R - L + 1;
        else
            return 0;
    }

    public void solve() throws IOException {
        gen(0, 0, 0);
        Collections.sort(a);
        int t = nextInt();
        for (int i = 0; i < t; i++) {
            long l = nextLong();
            long r = nextLong();
            out.println(query(l, r));
        }
    }

    public void run() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        br.close();
        out.close();
    }

    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;

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

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

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

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

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