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 Main {
    static int[] arr;
    static int n;
    static int[][][] memo;
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
       int iter = scan.nextInt();
        for (int i = 0; i < iter; i++) {
            memo = new int[20][2][20];
            for (int[][] twoArr:memo) {
                for (int[] arr :twoArr) {
                    Arrays.fill(arr,-1);
                }
            }
            long temp = scan.nextLong() -1;
            String s = String.valueOf(temp);
           arr = new int[s.length()];
           n = s.length();
            for (int j = 0; j < s.length(); j++) {
                arr[j] = s.charAt(j)-'0';
            }
           int p1 =  dp(0,0,0);
            memo = new int[20][2][20];
            for (int[][] twoArr:memo) {
                for (int[] arr :twoArr) {
                    Arrays.fill(arr,-1);
                }
            }
            s = scan.next();
            n = s.length();
            arr = new int[s.length()];
            for (int j = 0; j < s.length(); j++) {
                arr[j] = s.charAt(j)-'0';
            }
            int p2 = dp(0,0,0);

           pw.println(p2-p1);
        }

        pw.flush();
        pw.close();
    }
    static int dp(int index, int bool, int nonZeroCount){
        if(nonZeroCount > 3)
            return 0;
        if(index == arr.length)
            return 1;
        if(memo[index][bool][nonZeroCount] != -1)
            return memo[index][bool][nonZeroCount];
        int ans = 0;
        int upperBound = 9;
        if(bool == 0)
            upperBound = arr[index];
        for (int i = 0; i <= upperBound ; i++) {
            int newBool = bool;
            int newNonZeroCount = nonZeroCount;
            if(i != 0)
                newNonZeroCount ++;
            if(i != upperBound)
                newBool = 1;
            ans += dp(index + 1,newBool,newNonZeroCount);
        }
        return memo[index][bool][nonZeroCount] = ans;
    }
    static class Scanner
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

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

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

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

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

        public double nextDouble() throws IOException
        {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if(x.charAt(0) == '-')
            {
                neg = true;
                start++;
            }
            for(int i = start; i < x.length(); i++)
                if(x.charAt(i) == '.')
                {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                }
                else
                {
                    sb.append(x.charAt(i));
                    if(dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg?-1:1);
        }

        public boolean ready() throws IOException {return br.ready();}

    }
}