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:
t = int(input())
arr = []
for i in range(1, 19):
    arr.append((i - 1) * (i - 2) // 2 * 9 * 9 * 9 + (i - 1) * 9 * 9 + 9)
pref = [0]
for i in arr:
    pref.append(pref[-1] + i)

def f(x):
    if x == 0:
        return 0
    s = str(x)
    n = len(s)
    ans = pref[n - 1]
    cnt = 0
    for i in range(n):
        a = int(s[i])
        if a != 0:
            if cnt == 0:
                ans += (a - 1) * (n - i - 1) * (n - i - 2) // 2 * 9 * 9 + (a - 1) * (n - i - 1) * 9 + (a - 1)
                cnt += 1
            elif cnt == 1:
                ans += (n - i - 1) * (n - i - 2) // 2 * 9 * 9 + (n - i - 1) * 9 + 1
                if a != 1:
                    ans += (a - 1) * (n - i - 1) * 9 + (a - 1)
                cnt += 1
            elif cnt == 2:
                ans += (n - i - 1) * 9 + 1
                if a != 1:
                    ans += (a - 1)
                cnt += 1
                break
    return ans + 1
            
for i in range(t):
    l, r = map(int, input().split())
    l -= 1
    print(f(r) - f(l))    

'''n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

l = 0
r = 0
if arr1[l] == arr2[r]
'''
'''
n, k = map(int, input().split())
print((k + n - 1) // n)
'''