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:
//package com.prituladima.codeforce.contests.contest1036;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.IntStream;

import static java.lang.Double.parseDouble;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.util.Arrays.stream;
import static java.util.stream.IntStream.range;

//https://codeforces.com/contest/1036

public class C {

    long NAXI = 9223372036854775807L;
    long MAXC = 1000000000000000000L;

    private void pregen() {
        char[] number = new char[18];
        Arrays.fill(number, '0');

        //1
        for (int i = 17; i >= 0; i--) {
            for (char j = '1'; j <= '9'; j++) {
                number[i] = j;
                long newV = Long.parseLong(new StringBuilder().append(number).toString());
                LIST.add(newV);
                number[i] = '0';
            }
        }

        //2
        for (int i = 17; i >= 0; i--) {
            for (char j = '1'; j <= '9'; j++) {

                for (int i2 = 17; i2 >= 0; i2--) {
                    for (char j2 = '1'; j2 <= '9'; j2++) {
                        if (i > i2) {
                            number[i] = j;
                            number[i2] = j2;
                            long newV = Long.parseLong(new StringBuilder().append(number).toString());
                            LIST.add(newV);
                            number[i] = '0';
                            number[i2] = '0';

                        }
                    }
                }
            }
        }


        //3
        for (int i = 17; i >= 0; i--) {
            for (char j = '1'; j <= '9'; j++) {

                for (int i2 = 17; i2 >= 0; i2--) {
                    for (char j2 = '1'; j2 <= '9'; j2++) {

                        for (int i3 = 17; i3 >= 0; i3--) {
                            for (char j3 = '1'; j3 <= '9'; j3++) {

                                if (i > i2 && i2 > i3) {
                                    number[i] = j;
                                    number[i2] = j2;
                                    number[i3] = j3;
                                    long newV = Long.parseLong(new StringBuilder().append(number).toString());
                                    LIST.add(newV);
                                    number[i] = '0';
                                    number[i2] = '0';
                                    number[i3] = '0';
                                }
                            }
                        }
                    }
                }
            }
        }


        LIST.add(MAXC);
        Collections.sort(LIST);
//        System.out.println(LIST.size());
    }

    private void solve() {
        pregen();
//        int k = nextInt();
//        while (k-- > 0){
//            soutnl(Classy_Numbers(nextLong(), nextLong()));
//        }
        IntStream.range(0, nextInt()).forEach((i) -> soutnl(Classy_Numbers(nextLong(), nextLong())));
    }

    List<Long> LIST = new ArrayList<>(30_000);

    private long Classy_Numbers(long L, long R) {
        if (L == 1)
            return Classy_Numbers(R);

        return Classy_Numbers(1, R) - Classy_Numbers(1, L - 1);
    }

    private long Classy_Numbers(long R) {
        return upperBound(LIST, R);
    }

    public static int upperBound(List<Long> array, long value) {
        int low = 0;
        int high = array.size();
        while (low < high) {
            final int mid = (low + high) / 2;
            if (value >= array.get(mid)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static int lowerBound(List<Long> array, int length, long value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = (low + high) / 2;
            if (value <= array.get(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }


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

    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter writer;

    private void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    private int nextInt() {
        return parseInt(nextToken());
    }

    private long nextLong() {
        return parseLong(nextToken());
    }

    private double nextDouble() {
        return parseDouble(nextToken());
    }

    private int[] nextArr(int size) {
        return stream(new int[size]).map(c -> nextInt()).toArray();
    }

    private long[] nextArrL(int size) {
        return stream(new long[size]).map(c -> nextLong()).toArray();
    }

    private double[] nextArrD(int size) {
        return stream(new double[size]).map(c -> nextDouble()).toArray();
    }

    private char[][] nextCharMatrix(int n) {
        return range(0, n).mapToObj(i -> nextToken().toCharArray()).toArray(char[][]::new);
    }

    private int[][] nextIntMatrix(final int n, final int m) {
        return range(0, n).mapToObj(i -> nextArr(m)).toArray(int[][]::new);
    }

    private double[][] nextDoubleMatrix(int n, int m) {
        return range(0, n).mapToObj(i -> nextArr(m)).toArray(double[][]::new);
    }

    private String nextToken() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    private void souf(String format, Object... args) {
        writer.printf(format, args);
    }

    private void sout(Object o) {
        writer.print(o);
    }

    private void newLine() {
        writer.println();
    }

    private void soutnl(Object o) {
        sout(o);
        newLine();
    }

    private int max(int a, int b) {
        return Math.max(a, b);
    }

    private int min(int a, int b) {
        return Math.min(a, b);
    }


}