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
from array import array  # noqa: F401


def readline(): return sys.stdin.buffer.readline().decode('utf-8')


q = int(readline())
ans = [0]*q


def solve(x):
    if x == 0:
        return 0

    s = str(x)
    dp = [[0]*5 for _ in range(len(s))]
    for i in range(int(s[0])):
        dp[0][1 if i > 0 else 0] += 1

    bc = 1
    for i, d in enumerate(map(int, s[1:]), start=1):
        for j in range(4):
            for k in range(10):
                dp[i][j+(1 if k > 0 else 0)] += dp[i-1][j]
        if bc < 4:
            for k in range(d):
                dp[i][bc + (1 if k > 0 else 0)] += 1

        bc += 1 if d > 0 else 0

    return sum(dp[-1][:4]) + (1 if bc < 4 else 0) - 1


for i in range(q):
    l, r = map(int, readline().split())
    ans[i] = solve(r) - solve(l-1)

print(*ans, sep='\n')