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 javafx.util.Pair;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

/**
 * Created by timur on 28.03.15.
 */

public class TaskC {
    boolean eof;
    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

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

    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return "-1";
            }
        }
        return st.nextToken();
    }

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

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

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

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


    void run() throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        try {
            File f = new File("a.in");
            if (f.exists() && f.canRead()) {
                input = new FileInputStream(f);
                output = new PrintStream("a.out");
            }
        } catch (Throwable e) {
        }
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(output);
        solve();
        br.close();
        out.close();
    }


    void solve() {
        TreeSet<Long> nums = new TreeSet<>();
        for (int i = 0; i < 1001; i++) {
            nums.add((long) i);
        }
        long[] tmul = new long[20];
        tmul[0] = 1;
        tmul[1] = 10;
        for (int i = 2; i < 20; i++) {
            tmul[i] = tmul[i - 1] * 10;
        }
        long cur, c2;
        for (int i = 3; i < 18; i++) {
            for (int k = 0; k < 10; k++) {
                for (int pos1 = 0; pos1 < i; pos1++) {
                    cur = ((long) k) * tmul[pos1];
                    for (int f = 0; f < 10; f++) {
                        for (int pos2 = pos1; pos2 < i; pos2++) {
                            c2 = cur + ((long) f) * tmul[pos2];
                            for (int j = 1; j < 10; j++) {
                                if (((long) j) * tmul[i] + c2 < 0) {
                                    int x = 3;
                                }
                                nums.add(((long) j) * tmul[i] + c2);
                            }
                        }
                    }
                }
            }
        }
        nums.add(tmul[18]);
        long[] ff = new long[nums.size()];
        int pos = 0;
        for (Long f : nums) {
            ff[pos] = f;
            pos++;
        }
        //Arrays.sort(ff);
        int t = nextInt(), p1, p2, ip= 0;
        long l, r;
        for (int i = 0; i < t; i++) {
            l = nextLong() - 1;
            r = nextLong();
            p1 = Arrays.binarySearch(ff, l);
            if (p1 >= 0) {
                p1++;
            } else {
                p1 = -(p1 + 1);
            }
            p2 = Arrays.binarySearch(ff, r);
            if (p2 >= 0) {
                p2++;
            } else {
                p2 = -(p2 + 1);
            }
            out.println(p2 - p1);
        }
    }
}