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 \le x \le 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 \le T \le 10^4$) — the number of segments in a testcase.

Each of the next $T$ lines contains two integers $L_i$ and $R_i$ ($1 \le L_i \le R_i \le 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

Difficulty: interview

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

# this math tutorial is boring

classy=set()

for i in range(19):
    for j in range(i):
        for k in range(j):
            for a in range(10):     # a=0 for good measure
                for b in range(10):
                    for c in range(10):
                        what=a*10**i+b*10**j+c*10**k
                        classy.add(what)

li=sorted(classy)

def counting(i):
    # return len([x for x in li if x <= i])+C
    lo=0
    hi=len(li)-1
    while lo<hi:
        mid=(lo+hi+1)//2
        if li[mid]<=i:
            lo=mid
        else:
            hi=mid-1
    return lo

for _ in range(int(input())):
    a,b=map(int,input().split())
    print(counting(b)-counting(a-1))

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except ModuleNotFoundError:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
def memo(func):  
    cache={}  
    def wrap(*args):  
        if args not in cache:  
            cache[args]=func(*args)  
        return cache[args]  
    return wrap

@memo
def comb (n,k):
    if k>n: return 0    
    if k==0: return 1
    if n==k: return 1
    return comb(n-1,k-1) + comb(n-1,k)
def getclam(K, left = 3):
    if K==0: return 1
    if left ==0: return 1
    s = str(K)
    l = len(s)

    r = 0
    x = int(s[0])
    if l>1:
        for i in range(left+1):
            r += comb(l-1,i) * 9 ** i
        if x>0:
            for i in range(left):
                r += comb(l-1,i) * 9 ** i * (x-1)
        s1 = s[1:]
        y = 0
        if s1:
            y = int(s1)
        if x!=0:
            left-=1
        r+= getclam( y, left)
        return r
    else:
        return x+1
for i in range(1000, 1100):
    continue
    dprint(i, getclam(i))

for _ in range(N):
    L,R = getIntList()
    r = getclam(R) - getclam(L-1)
    print(r)







USE_STDIO = False

if not USE_STDIO:
    try: import mypc
    except: pass

def Cnk(n, k):
    ans = 1
    for i in range(k):
        ans *= n - i
        ans //= i + 1
    return ans

def main():
    num = [[0] * 4 for _ in range(19)]
    for i in range(19):
        for j in range(4):
            if j: num[i][j] += num[i][j-1]
            if i >= j:
                num[i][j] += 9 ** j * Cnk(i, j)
    
    def count(n):
        if n == 0: return 0
        n = list(map(int, str(n)))
        l = len(n)
        ans = 0
        for i in range(1, l):
            ans += 9 * num[i - 1][2]
        cur = 3
        for i in range(l):
            if n[i] > 0:
                ans += (n[i] - 1) * num[l - i - 1][cur - 1]
                if i: ans += num[l - i - 1][cur]
                cur -= 1
                if cur <= 0: break
        ans += 1
        return ans

    q,  = list(map(int, input().split(' ')))
    for _ in range(q):
        L, R = list(map(int, input().split(' ')))
        ans = count(R) - count(L - 1)
        print(ans)

def __starting_point():
    main()




__starting_point()

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)
'''

def f(n):
    if n == 0:
        return 1
    dp = [[[0] * 2 for j in range(4)] for z in range(len(n))]
    dp[0][3][0] = 1
    dp[0][2][0] = int(n[0]) - 1
    dp[0][2][1] = 1
    for i in range(1, len(n)):
        for j in range(4):
            if n[i] == '0':
                dp[i][j][0] += dp[i - 1][j][0]
                dp[i][j][1] += dp[i - 1][j][1]
            else:
                dp[i][j][0] += dp[i - 1][j][0] + dp[i - 1][j][1]
            for z in range(1, 10):
                if z < int(n[i]):
                    if j < 3:
                        dp[i][j][0] += dp[i - 1][j + 1][0] + dp[i - 1][j + 1][1]
                elif z == int(n[i]):
                    if j < 3:
                        dp[i][j][0] += dp[i - 1][j + 1][0]
                        dp[i][j][1] += dp[i - 1][j + 1][1]
                else:
                    if j < 3:
                        dp[i][j][0] += dp[i - 1][j + 1][0]

    res = 0
    for j in range(4):
        res += dp[len(n) - 1][j][0] + dp[len(n) - 1][j][1]
    return res

t = int(input())
while t:
    t -= 1
    l, r = list(map(int, input().split()))
    print(f(str(r)) - f(str(l - 1)))


def f(n):
    if n == 0:
        return 1
    dp = [[[0] * 2 for j in range(4)] for z in range(len(n))]
    dp[0][3][0] = 1
    dp[0][2][0] = int(n[0]) - 1
    dp[0][2][1] = 1
    for i in range(1, len(n)):
        for j in range(4):
            if n[i] == '0':
                dp[i][j][0] += dp[i - 1][j][0]
                dp[i][j][1] += dp[i - 1][j][1]
            else:
                dp[i][j][0] += dp[i - 1][j][0] + dp[i - 1][j][1]
            if j >= 3:
                continue
            for z in range(1, 10):
                if z < int(n[i]):
                    dp[i][j][0] += dp[i - 1][j + 1][0] + dp[i - 1][j + 1][1]
                elif z == int(n[i]):
                    dp[i][j][0] += dp[i - 1][j + 1][0]
                    dp[i][j][1] += dp[i - 1][j + 1][1]
                else:
                    dp[i][j][0] += dp[i - 1][j + 1][0]

    res = 0
    for j in range(4):
        res += dp[len(n) - 1][j][0] + dp[len(n) - 1][j][1]
    return res

t = int(input())
while t:
    t -= 1
    l, r = list(map(int, input().split()))
    print(f(str(r)) - f(str(l - 1)))


def C(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) // (i + 1);
    return ret

def f(N):
    N = [int(ch) for ch in reversed(str(N))]
    cnt, nonzero = 0, 0
    for k in range(len(N)-1, -1, -1):
        if N[k] > 0:
            for i in range(4 - nonzero):
                cnt += C(k, i) * pow(9, i)
            nonzero += 1
            for i in range(4 - nonzero):
                cnt += (N[k] - 1) * C(k, i) * pow(9, i)
        if nonzero > 3:
            break
    return cnt

for run in range(int(input())):
    l, r = list(map(int, input().split()))
    print(f(r+1) - f(l))


def C(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) // (i + 1);
    return ret

def f(N):
    N = [int(ch) for ch in reversed(str(N))]
    cnt, nonzero = 0, 0
    for k in range(len(N)-1, -1, -1):
        if N[k] > 0:
            for i in range(4 - nonzero):
                cnt += C(k, i) * pow(9, i)
            nonzero += 1
            for i in range(4 - nonzero):
                cnt += (N[k] - 1) * C(k, i) * pow(9, i)
        if nonzero > 3:
            break
    return cnt

for run in range(int(input())):
    l, r = map(int, input().split())
    print(f(r+1) - f(l))

def cnt(l, c):
    if l <= c:
        return 10**c
    res = 1
    if c > 0: res += l*9
    if c > 1: res += l*(l-1)*9*9//2
    if c > 2: res += l*(l-1)*(l-2)*9*9*9//6
    return res

def calc(n, c):
    x=str(n)
    xn = len(x)
    if xn <= c:
        return n+1
    res = cnt(xn-1, c)+1
    d = int(x[0])
    if d > 1:
        res += cnt(xn-1, c-1)*(d - 1)
    if c > 1:
        for i in range(1,xn):
            d = int(x[i])
            if d != 0:
                res += calc(int(x[i:]), c-1)-1
                break
    return res
"""ans=0
for i in range(90000):
    s = str(i)
    if len(s)-s.count('0') < 3:
        ans+=1
print(ans)"""

#ans=calc(1000000,3) # 15850
t = int(input())
for i in range(t):
    l,r = map(int, input().split())
    print(calc(r,3)-calc(l-1,3))

from bisect import bisect_left as bl
c=[]
def gen(n,nz):
    if len(n)>=19:
        return
    nonlocal c
    c.append(int(n))
    if nz==3:
        n+="0"
        gen(n,nz)
        return
    gen(n+"0",nz)
    for i in ("123456789"):
        gen(n+i,nz+1)
for i in ("123456789"):
    gen(i,1)
c.append(10**18)
c.sort()
n=int(input())
for i in range(n):
    a,b=list(map(int,input().split()))
    x=min(bl(c,b),len(c)-1)
    y=bl(c,a)
    if x==y and b<c[x]:
        print(0)
    elif (c[x]==b and c[y]==a) or c[x]==b:
        print(x-y+1)
    else:
        print(x-y)

        


import math
def combi(L,n):
    return math.factorial(L)//math.factorial(n)//math.factorial(L-n)


T=int(input())
LR=[list(map(int,input().split())) for i in range(T)]

def classy(less,nonzero,now):
    L=len(str(now))

    if less==0:
        if 3-nonzero>=L:
            return 10**L
        else:
            ANS=1
            for i in range(1,3-nonzero+1):
                ANS+=combi(L,i)*(9**i)

            return ANS

    else:
        if nonzero<=2:
            if now<=9:
                return now+1
            
            else:
                if int(str(now)[0])==1:
                    return classy(1,nonzero+1,int(str(now)[1:]))\
                           +classy(0,nonzero,int("9"*(L-1)))\

                else:
                    return classy(1,nonzero+1,int(str(now)[1:]))\
                           +(int(str(now)[0])-1)*classy(0,nonzero+1,int("9"*(L-1)))\
                           +classy(0,nonzero,int("9"*(L-1)))

        else:
            return 1

for l,r in LR:
    print(classy(1,0,r)-classy(1,0,l-1))

            
        
                          
        
    
    


import math
def combi(L,n):
    return math.factorial(L)//math.factorial(n)//math.factorial(L-n)


T=int(input())
LR=[list(map(int,input().split())) for i in range(T)]

def classy(less,nonzero,now):
    L=len(str(now))

    if less==0:
        if 3-nonzero>=L:
            return 10**L
        else:
            ANS=1
            for i in range(1,3-nonzero+1):
                ANS+=combi(L,i)*(9**i)

            return ANS

    else:
        if nonzero<=2:
            if now<=9:
                return now+1
            
            else:
                if int(str(now)[0])==1:
                    return classy(1,nonzero+1,int(str(now)[1:]))\
                           +classy(0,nonzero,int("9"*(L-1)))\

                else:
                    return classy(1,nonzero+1,int(str(now)[1:]))\
                           +(int(str(now)[0])-1)*classy(0,nonzero+1,int("9"*(L-1)))\
                           +classy(0,nonzero,int("9"*(L-1)))

        else:
            return 1

for l,r in LR:
    print(classy(1,0,r)-classy(1,0,l-1))

            
        
                          
        
    
    



dp = [[-1]*20 for _ in range(5)]
def dfs(pos, cnt, limited, dp, nums):
	if cnt > 3:
		return 0
	if pos == -1:
		return 1
	if not limited and dp[cnt][pos] != -1:
		return dp[cnt][pos]
	upper = nums[pos] if limited else 9
	tmp = 0
	for i in range(upper + 1):
		tmp += dfs(pos - 1, cnt + (i > 0), limited&(i==upper), dp, nums)
	if not limited:
		dp[cnt][pos] = tmp
	return tmp
def classy(num):
	nums = []
	while num:
		nums.append(num % 10)
		num //= 10
	
	return dfs(len(nums) - 1, 0, 1, dp, nums)


def __starting_point():
	T = int(input())
	for _ in range(T):
		L, R = map(int, input().split())
		print(classy(R) - classy(L-1))
__starting_point()

import sys
class Solution():
    mem = dict()

    def classy_Numbers(self):
        T = int(sys.stdin.readline().strip())
        self.queries = []
        for t in range(T):
            left, right = list(map(int, sys.stdin.readline().strip().split()))
            print(self.dp(right, 3) - self.dp(left-1, 3))

    def dp(self, target, limit):
        num_digits = len(str(target))
        if (target, limit) in self.mem:
            return self.mem[(target, limit)]
        if limit == 0:
            return 1
        if num_digits <= limit:
            return target + 1

        top_digit = target // (10 ** (num_digits-1))
        res = target % (10 ** (num_digits-1))
        ret = self.dp(res, limit-1) \
                + max(top_digit-1, 0) * self.dp(10**(num_digits-1)-1, limit-1) \
                + self.dp(10**(num_digits-1)-1, limit)
        self.mem[(target, limit)] = ret
        return ret

sol = Solution()
sol.classy_Numbers()
# print(sol.dp(1, 3))
# print(sol.dp(1234, 4, 3))
# print(sol.dp(12345, 5, 3))


import math

def check(x):
    cnt = 0
    while(x):
        cnt = cnt + (x%10 != 0)
        x = math.floor(x/10)
    return cnt<=3

def bl(x):
    ans = 0
    for i in range(1,x+1):
        if check(i):
            ans = ans+1
    return ans


def jc(x):
    sm = 1
    for i in range(1,x+1):
        sm = sm * i
    return sm

def c(x,y):
    if x<y:
        return 0
    return jc(x)/(jc(x-y)*jc(y))

def cal1(x,y):
    ans = 0
    for i in range(1,min(x,y)+1):
        ans = ans + c(x,i)*(9**i)
    return ans+1

def revers(x):
    ans = 0
    while(x):
        ans = ans*10+ x%10
        x = x.__floordiv__(10)

    return ans

def cal2(x):
    rx = revers(x)
    ans = 0
    cnt = 0
    l = 0
    l_ = 0
    while(x):
        l = l+1
        x = x.__floordiv__(10)


    while(rx):
        now = rx % 10
        rx = rx.__floordiv__(10)
        l_ = l_ + 1
        if now!=0:
            cnt = cnt+1
        else:
            continue
        ans = ans + (now-1)*cal1(l-l_,3-cnt) + cal1(l-l_,3-cnt+1)

        if cnt>=3:
            break

    return ans

T = int(input())
for i in range(T):

    x,y = list(map(int,input().split()))

    print(int(cal2(y)-cal2(x-1)))


from itertools import combinations

all_classy = []

def all_possible(a):
    if len(a) == 0:
        return [['0']*19]
    lower = all_possible(a[1:])
    ans = []
    for l in lower:
        for x in range(1, 10):
            this = l[:]
            this[a[0]] = str(x)
            ans.append(this)
    return ans

for i in range(1, 4):
    for a in combinations(range(19), i):
        this_possible = all_possible(a)
        this_possible = [int(''.join(x)) for x in this_possible]
        all_classy += this_possible

all_classy.sort()

def ge(num):
    if num == 1:
        return 0
    lower, upper = 0, len(all_classy)
    while lower < upper - 1:
        mid = (lower+upper)>>1
        if(all_classy[mid] < num):
            lower = mid
        else:
            upper = mid

    return upper


def le(num):
    lower, upper = 0, len(all_classy)
    while lower < upper-1:
        mid = (lower+upper)>>1
        if all_classy[mid] > num:
            upper = mid
        else:
            lower = mid

    return lower

q = int(input())

for i in range(q):
    l, r = map(int, input().strip().split())
    x, y = ge(l), le(r)
    print(y-x+1)

import sys

MAX_N = 20
MAX_DIG = 3
dp = [[0] * (MAX_DIG + 1) for i in range(MAX_N)]

def calc_dp():
    dp[0][0] = 1
    for i in range(1, MAX_N):
        dp[i][0] = 1
        for j in range(MAX_DIG):
            dp[i][j + 1] += 9 * dp[i - 1][j]
            dp[i][j + 1] += dp[i - 1][j + 1]

def first_dig(n):
    cnt = 0
    while n >= 10:
        n //= 10
        cnt += 1
    return n, cnt

def calc_ans(n):
    ans = 0
    for n_digs in range(MAX_DIG, -1, -1):
        x, cnt = first_dig(n)
        for i in range(n_digs):
            ans += x * dp[cnt][i]
        ans += dp[cnt][n_digs]
        n -= x * 10 ** cnt
    return ans

def main():
    calc_dp()
    T = int(input())
    for _ in range(T):
        l, r = map(int, input().split())
        print(calc_ans(r) - calc_ans(l - 1) if l > 0 else 0)

def __starting_point():
    main()
__starting_point()

import sys

MAX_N = 20
MAX_DIG = 3
dp = [[0] * (MAX_DIG + 1) for i in range(MAX_N)]

def calc_dp():
    dp[0][0] = 1
    for i in range(1, MAX_N):
        dp[i][0] = 1
        for j in range(MAX_DIG):
            dp[i][j + 1] += 9 * dp[i - 1][j]
            dp[i][j + 1] += dp[i - 1][j + 1]

def first_dig(n):
    cnt = 0
    while n >= 10:
        n //= 10
        cnt += 1
    return n, cnt

def calc_ans(n):
    ans = 0
    for n_digs in range(MAX_DIG, -1, -1):
        x, cnt = first_dig(n)
        for i in range(n_digs):
            ans += x * dp[cnt][i]
        ans += dp[cnt][n_digs]
        n -= x * 10 ** cnt
    return ans

def main():
    calc_dp()
    T = int(input())
    for _ in range(T):
        l, r = map(int, input().split())
        print(calc_ans(r) - calc_ans(l - 1) if l > 0 else 0)

def __starting_point():
    main()
__starting_point()

import sys

MAX_N = 20
MAX_DIG = 3
dp = [[0] * (MAX_DIG + 1) for i in range(MAX_N)]

def calc_dp():
    dp[0][0] = 1
    for i in range(1, MAX_N):
        dp[i][0] = 1
        for j in range(MAX_DIG):
            dp[i][j + 1] += 9 * dp[i - 1][j]
            dp[i][j + 1] += dp[i - 1][j + 1]

def first_dig(n):
    cnt = 0
    while n >= 10:
        n //= 10
        cnt += 1
    return n, cnt

def calc_ans(n):
    ans = 0
    for n_digs in range(MAX_DIG, -1, -1):
        x, cnt = first_dig(n)
        for i in range(n_digs):
            ans += x * dp[cnt][i]
        ans += dp[cnt][n_digs]
        n -= x * 10 ** cnt
    return ans

def main():
    calc_dp()
    T = int(input())
    for _ in range(T):
        l, r = map(int, input().split())
        print(calc_ans(r) - calc_ans(l - 1))

def __starting_point():
    main()
__starting_point()

com = [[0]*19 for i in range(19)]


def solve(x):
    sx, non_zero, res = str(x), 3, 0

    for i in range(len(sx)):
        if not int(sx[i]):
            continue

        for j in range(0, non_zero+1):
            res += com[len(sx)-i-1][j] * 9 ** j

        non_zero -= 1

        if non_zero == -1:
            break

        for j in range(0, non_zero+1):
            res += (int(sx[i])-1) * com[len(sx)-i-1][j] * 9 ** j

    return res


def main():
    t = int(input())

    for i in range(19):
        com[i][0] = 1
    for i in range(1, 19):
        for j in range(1, i+1):
            com[i][j] = com[i-1][j] + com[i-1][j-1]

    for i in range(t):
        l, r = list(map(int, input().split()))
        print(solve(r+1)-solve(l))


def __starting_point():
    main()

__starting_point()

t=int(input())
l=[]
r=[]
for i in range (t):
    q,w=[int(el) for el in input().split()]
    l.append(q)
    r.append(w)

def count(x):
    if x<=1110:
        return x
    s=str(x)
    n=len(s)
    cz=3
    out=0
    for i in range(n-2): #пробежали до сотен
        a=int(s[i])
        k = n - i - 1  # осталось знаков после i

        if a>0:
            if cz==3:
                out=out+k*(k-1)*(k-2)/6*9*9*9+k*(k-1)/2*9*9+k*9
            elif cz==2:
                out=out+k*(k-1)/2*9*9+k*9+1
            elif cz==1:
                out=out+k*9+1
            cz=cz-1

            if cz==2:
                plus=k*(k-1)/2*9*9+k*9+1
            elif cz==1:
                plus=k*9+1
            elif cz==0:
                plus=1
            out=out+plus*(a-1)
        if cz==0:
            break
    if cz==0:
        out=out+1
        return out
    if cz==1:
#        out=out+1+int(s[n-2])
        if int(s[n-2])>0:
            out=out+int(s[n-2])+10
        else:
            out=out+1+int(s[n-1])
        return out
    out=out+int(s[n-2:])+1
    return out

for i in range(t):
    a=int(count(r[i]))
    b=int(count(l[i]-1))
    print(a-b)




import bisect as b

from collections import OrderedDict

num =[]

def Classy (pos, count, current):
    if pos==18:
        num.append(current)
        return
    Classy(pos+1, count, current*10)
    
    if (count < 3 ):
        for i in range(1,10):
            Classy(pos+1, count+1, current *10 + i)
    
Classy(0,0,0)

num=list(OrderedDict.fromkeys(num))

num.pop(0)

num.insert(len(num)+1, 1000000000000000000)



T = int(input())

while(0 < T):
    L, R = [int(x) for x in input().split(' ')]
    
    ans = b.bisect_right(num, R, lo=0, hi=len(num)) - b.bisect_left(num, L, lo=0, hi=len(num))
    print(int(ans))
    
    T=T-1