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

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Combinatorics


Solutions:
from sys import stdin
C = [[0] * 20 for _ in range(20)]
for i in range(20):
	C[i][0] = C[i][i] = 1
	for j in range(1, i):
		C[i][j] = C[i - 1][j] + C[i - 1][j - 1]
pw = [1, 9, 81, 729]

def get(n, lft):
	return sum((C[n][i] * pw[i] for i in range(lft + 1) if 0 <= i <= n))

def calc(x):
	s = str(x)
	res = 0
	cur = 3
	n = len(s)
	for i in range(n):
		if s[i] == '0':
			continue
		res += get(n - i - 1, cur)
		cur -= 1
		if cur == -1:
			break
		res += get(n - i - 1, cur) * (int(s[i]) - 1)
	return res
stdin.readline()
test = stdin.readlines()
output = []
for line in test:
	(L, R) = map(int, line.split())
	ans = calc(R + 1) - calc(L)
	output.append(ans)
print('\n'.join(map(str, output)))


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
		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:
		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 sys
from array import array

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


from sys import stdin, stdout
pw = [1, 9, 81, 729]
C = [[0 for _ in range(20)] for _ in range(20)]

def Cn_k(n: int, k: int):
	if k < 0 or k > n:
		return 0
	return C[n][k]

def get(n: int, lft: int):
	total = 0
	for i in range(lft + 1):
		total += Cn_k(n, i) * pw[i]
	return total

def calc(x: int):
	sx = str(x)
	ans = 0
	cur = 3
	n = len(sx)
	for i in range(n):
		if sx[i] == '0':
			continue
		ans += get(n - i - 1, cur)
		cur -= 1
		if cur == -1:
			break
		ans += get(n - i - 1, cur) * (int(sx[i]) - 1)
	return ans
for i in range(20):
	C[i][0] = C[i][i] = 1
	for j in range(1, i):
		C[i][j] = C[i - 1][j] + C[i - 1][j - 1]
to_int = lambda x: int(x)
T = list(map(to_int, stdin.readline().split()))[0]
intervals = [list(map(to_int, stdin.readline().split())) for i in range(T)]
res = [calc(intervals[i][1] + 1) - calc(intervals[i][0]) for i in range(T)]
for i in range(T):
	stdout.write('{}\n'.format(res[i]))


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


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


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) = map(int, input().split())
	print(f(str(r)) - f(str(l - 1)))


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) = map(int, input().split())
	print(int(cal2(y) - cal2(x - 1)))


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


from sys import stdin
digs = [[1, 0, 0, 0], [1, 9, 0, 0]]
for x in range(18):
	last = digs[-1]
	temp = last[:]
	temp[1] += last[0] * 9
	temp[2] += last[1] * 9
	temp[3] += last[2] * 9
	digs.append(temp)

def classyNums(num):
	s = str(num)
	total = 0
	things = 0
	for (i, x) in enumerate(s):
		nX = int(x)
		if nX:
			ind = len(s) - i
			total += sum(digs[ind - 1]) * nX
			total -= digs[ind - 1][3] * (nX - 1)
			if things > 0:
				total -= digs[ind - 1][2] * (nX - 1)
				total -= digs[ind - 1][3]
			if things > 1:
				total -= digs[ind - 1][1] * (nX - 1)
				total -= digs[ind - 1][2]
			if things > 2:
				total -= digs[ind - 1][0] * (nX - 1)
				total -= digs[ind - 1][1]
			if things > 3:
				total -= digs[ind - 1][0]
			things += 1
	if s.count('0') + 3 >= len(s):
		total += 1
	return total
for case in range(int(stdin.readline())):
	(l, r) = [int(x) for x in stdin.readline().split()]
	print(classyNums(r) - classyNums(l - 1))


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


import sys
input = sys.stdin.readline
classy = set()
for i in range(19):
	for j in range(i):
		for k in range(j):
			for a in range(10):
				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):
	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 sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())

def f(X):
	digit = len(X)
	dp = [[[0] * 4 for _ in range(2)] for _ in range(digit + 1)]
	dp[0][0][0] = 1
	for d in range(digit):
		x = X[d]
		for i in range(2):
			for j in range(4):
				upper = 9 if i else x
				for k in range(upper + 1):
					if j + (k != 0) <= 3:
						dp[d + 1][i | (k < x)][j + (k != 0)] += dp[d][i][j]
	res0 = sum(dp[-1][0])
	res1 = sum(dp[-1][1])
	return (res0, res1)
t = I()
for _ in range(t):
	(L, R) = S().split()
	L = [int(l) for l in L]
	R = [int(r) for r in R]
	(l0, l1) = f(L)
	(r0, r1) = f(R)
	ans = r0 + r1 - l1
	print(ans)


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)

def solve(x, i, sml, nonz):
	if nonz > 3:
		return 0
	if i == len(x):
		if nonz > 3:
			return 0
		return 1
	global dp
	if dp[i][sml][nonz] != -1:
		return dp[i][sml][nonz]
	ans = 0
	for di in range(x[i] + 1):
		if di == 0:
			ans += solve(x, i + 1, di < x[i] or sml, nonz)
		else:
			ans += solve(x, i + 1, di < x[i] or sml, nonz + 1)
	if sml:
		for di in range(x[i] + 1, 10):
			ans += solve(x, i + 1, sml, nonz + 1)
	dp[i][sml][nonz] = ans
	return ans
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	x -= 1
	x = list(map(int, list(str(x))))
	y = list(map(int, list(str(y))))
	dp = [[[-1 for i in range(4)] for i in range(2)] for i in range(len(y))]
	y = solve(y, 0, False, 0)
	dp = [[[-1 for i in range(4)] for i in range(2)] for i in range(len(x))]
	x = solve(x, 0, False, 0)
	print(y - x)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())

def calc(x):
	s = str(x)
	n = len(s)
	dp = [[[0] * 2 for i in range(5)] for j in range(n + 1)]
	dp[0][0][0] = 1
	for i in range(n):
		for j in range(5):
			for k in range(2):
				nd = int(s[i])
				for d in range(10):
					ni = i + 1
					nj = j
					nk = k
					if d != 0:
						nj = min(nj + 1, 4)
					if k == 0:
						if d > nd:
							continue
						elif d < nd:
							nk = 1
						else:
							pass
					dp[ni][nj][nk] += dp[i][j][k]
	res = 0
	for j in range(4):
		for k in range(2):
			res += dp[n][j][k]
	return res
for _ in range(t):
	(l, r) = map(int, input().split())
	print(calc(r) - calc(l - 1))


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,) = map(int, input().split(' '))
	for _ in range(q):
		(L, R) = map(int, input().split(' '))
		ans = count(R) - count(L - 1)
		print(ans)
main()


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

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


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	for _ in range(N()):
		(l, r) = RL()
		from functools import lru_cache

		def dp(num):
			arr = []
			while num > 0:
				arr.append(num % 10)
				num //= 10

			@lru_cache(None)
			def ddp(pos, tag, znum):
				if pos < 0:
					return 1
				res = 0
				for i in range(10):
					if tag and i > arr[pos]:
						break
					if i != 0 and znum + 1 > 3:
						break
					res += ddp(pos - 1, tag and arr[pos] == i, znum + (1 if i != 0 else 0))
				return res
			return ddp(len(arr) - 1, True, 0)
		print(dp(r) - dp(l - 1))
main()


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
	elif nonzero <= 2:
		if now <= 9:
			return now + 1
		elif 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))


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
t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	print(calc(r, 3) - calc(l - 1, 3))


def ncr(n, r):
	return int(fact(n) / (fact(r) * fact(n - r)))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def f(s):
	j = 0
	ans = 0
	cnt = 0
	n = len(s)
	while j < n:
		if int(s[j]) != 0:
			for k in range(3 - cnt + 1):
				if k <= n - j - 1:
					ans += ncr(n - j - 1, k) * 9 ** k
			for k in range(3 - cnt):
				if k <= n - j - 1:
					ans += (int(s[j]) - 1) * (ncr(n - j - 1, k) * 9 ** k)
			cnt += 1
		if cnt == 3:
			break
		j += 1
	return ans
t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	print(f(str(r)) - f(str(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
from sys import stdin, stdout

def ncr(n, r):
	if n < r or r < 0 or n < 0:
		return 0
	if n - r < r:
		r = n - r
	arr = [0 for i in range(r + 1)]
	arr[0] = 1
	for i in range(n + 1):
		for j in range(min(i, r), 0, -1):
			arr[j] = arr[j] + arr[j - 1]
	return arr[r]

def getclassy(s):
	ans = 0
	nzd = 0
	for i in range(len(s)):
		if s[i] == '0':
			continue
		ans += sum([ncr(len(s) - i - 1, j) * 9 ** j for j in range(3 - nzd + 1)])
		nzd += 1
		if nzd == 4:
			break
		ans += sum([ncr(len(s) - i - 1, j) * 9 ** j for j in range(3 - nzd + 1)]) * (int(s[i]) - 1)
	return ans
t = int(stdin.readline())
for _ in range(t):
	(l, r) = map(int, stdin.readline().split(' '))
	r += 1
	l = list(str(l))
	r = list(str(r))
	stdout.write(str(getclassy(r) - getclassy(l)) + '\n')


def classy(ran, nb):
	p = len(ran)
	if p == 0 or nb == 0:
		return 0
	elif p <= nb:
		return int(ran)
	elif nb == 0:
		return 1
	elif ran[0] == '0':
		return classy(ran[1:], nb)
	else:
		p -= 1
		k = 1
		s = 1
		for i in range(nb - 1):
			k *= (p - i) / (i + 1)
			s += k * 9 ** (i + 1)
		k *= (p - nb + 1) / nb
		s = (int(ran[0]) - 1) * s + s + k * 9 ** nb
		return s + classy(ran[1:], nb - 1)
t = int(input())
res = []
for i in range(t):
	ran = [j for j in input().split()]
	res.append(classy(ran[1], 3) - classy(str(int(ran[0]) - 1), 3))
for i in res:
	print(int(i))


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	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())
(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)


factorial = [1]
for x in range(1, 20):
	factorial.append(factorial[-1] * x)

def choose(n, x):
	global factorial
	return factorial[n] // (factorial[x] * factorial[n - x])

def func(a):
	string = str(a)
	tot = 0
	count = 0
	for x in range(len(string)):
		d = int(string[x])
		if d != 0:
			count += 1
			for y in range(3 - count + 1 + 1):
				tot += choose(len(string) - 1 - x, y) * 9 ** y
			for y in range(3 - count + 1):
				tot += (d - 1) * choose(len(string) - 1 - x, y) * 9 ** y
	return tot

def main():
	count = int(input())
	for _ in range(count):
		arr = input().split()
		print(func(int(arr[1]) + 1) - func(int(arr[0])))
main()


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):
		if easy_stop(state):
			return 0
		if pos == -1:
			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
	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))
main()


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 os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 998244353

def solve():
	dp = [[0 for j in range(4)] for i in range(20)]
	for i in range(20):
		dp[i][0] = 1
	for i in range(20):
		for j in range(1, 4):
			if i <= j:
				dp[i][j] = 10 ** i
			else:
				dp[i][j] = dp[i - 1][j] + 9 * dp[i - 1][j - 1]

	def calc(X):
		S = [int(s) for s in str(X)]
		lenS = len(S)
		count = -1
		res = 0
		for i in range(lenS):
			if S[i] > 0:
				count += 1
				res += dp[lenS - i - 1][3 - count]
				res += dp[lenS - i - 1][3 - count - 1] * (S[i] - 1)
			if count == 2:
				break
		return res
	for _ in range(getInt()):
		(L, R) = getInts()
		print(calc(R) - calc(L - 1))
	return
solve()


import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
for t in range(1, T + 1):
	(l, r) = map(int, lines[t].strip().split(' '))

	def combi(L, count):
		res = 1
		for i in range(count):
			res *= L - i
		for i in range(1, count):
			res //= i + 1
		return res

	def solve(up, count):
		if count == 0:
			return 1
		st = str(up)
		res = 0
		L = len(st)
		if L <= count:
			return up + 1
		if L >= count + 1:
			for i in range(count + 1):
				res += combi(L - 1, i) * 9 ** i
		if L >= count:
			for i in range(count):
				res += combi(L - 1, i) * (int(st[0]) - 1) * 9 ** i
		res += solve(int(st[1:]), count - 1)
		return res
	print(solve(r, 3) - solve(l - 1, 3))


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