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 PYTHON3):

Solution:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')


from functools import lru_cache


def solve(x):
    default_state = 0

    def predicate(s):
        return s <= 3

    def new_state(s, pos, d):
        return s + (1 if d > 0 else 0)

    def easy_stop(s):
        return s > 3

    @lru_cache(maxsize=None)
    def go(pos, restricted, state):
        """
        :param pos: index value from right in the given integer
        :param restricted: if restricted, digit span is [0,9], otherwise [0,digits[pos]]
        :param state: supporting state
        :return:
        """
        if easy_stop(state):
            return 0

        if pos == -1:
            # matching condition
            return 1 if predicate(state) else 0

        ans = 0
        up = a[pos] if restricted else 9
        for d in range(up + 1):
            ans += go(pos - 1, restricted and d == a[pos], new_state(state, pos, d))
        return ans

    # digits array in reverse order
    a = []
    while x > 0:
        a.append(x % 10)
        x //= 10

    n = len(a)
    return go(n-1, True, default_state)


def solve_in_range(a, b):
    return solve(b) - solve(a-1)


def main():
    for _ in range(ri()):
        l, r = ria()
        wi(solve_in_range(l, r))


if __name__ == '__main__':
    main()