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

/**
 * @author: zhaoqing
 * @date: 2018/9/13
 * @time: 下午11:00
 */
public class ClassyNumbers {

    static Set<Long> set = new HashSet<>();

    private static void add(int len, int pos, int poos) {
        for (int i = 1; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= 9; k++) {
                    String a = "";
                    for (int l = 1; l <= len; l++) {
                        if (l == 1) {
                            a += i;
                        } else if (l == pos) {
                            a += j;
                        } else if (l == poos) {
                            a += k;
                        } else {
                            a += 0;
                        }


                    }
                    set.add(Long.parseLong(a));
                }
            }
        }
    }

    public static void main(String[] args) {
        for (long i = 0; i < 1000; i++) {
            set.add(i);
        }
        for (int len = 4; len <= 18; len++) {
            for (int i = 2; i < len; i++) {
                for (int j = i + 1; j <= len; j++) {
                    add(len, i, j);
                }
            }
        }
        set.add(1000000000000000000L);
        List<Long> list=new ArrayList<Long>(set);
        Collections.sort(list);
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            long b=sc.nextLong();
            long e=sc.nextLong();
            int bn=findBn(list,b);
            int en=findEn(list,e);
            int count=en-bn+1;
            System.out.println(count>0?count:0);
        }
    }
    private static int findBn(List<Long> list, long num){
        int middle = 0;
        int low = 0;
        int high = list.size() - 1;

        if (list.get(low) == num) {
            return low;
        } else if (list.get(high) == num) {
            return high;
        }

        while (low < high) {
            middle = (high + low + 1) / 2;
            if (list.get(middle) == num) {
                break;
            } else if (list.get(middle) > num) {
                high = middle;
            } else {
                low = middle;
            }
            if (high - low == 1) {
                middle=high;
                break;
            }
        }
        return middle;

    }
    private static int findEn(List<Long> list, long num){
        int middle = 0;
        int low = 0;
        int high = list.size() - 1;

        if (list.get(low) == num) {
            return low;
        } else if (list.get(high) == num) {
            return high;
        }

        while (low < high) {
            middle = (high + low + 1) / 2;
            if (list.get(middle) == num) {
                break;
            } else if (list.get(middle) > num) {
                high = middle;
            } else {
                low = middle;
            }
            if (high - low == 1) {
                middle=low;
                break;
            }
        }
        return middle;

    }
}