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

Solution:
'''input
4
1 1000
1024 1024
65536 65536
999999 1000001




'''
from collections import defaultdict as df
from bisect import bisect_left as bl 
import sys
from random import randint as R
from math import factorial as F
def c(n,r):
	if r>n:
		return 0
	if n<0:
		return 0
	if r<0:
		return 0
	return F(n)/(F(n-r)*F(r))

def get(n,zero):
	return (c(n,zero)*(9**zero))+(c(n,zero-1)*(9**(zero-1) ))+(c(n,(zero-2) )*(9**(zero-2) ))+(c(n,(zero-3) )*(9**(zero-3) ))

def solve(st,zero):
	st=str(int(st))
	if zero==0:
		return 0
	if len(st)<=zero:
		return int(st)
	ans= get(len(st)-1,zero)
	if int(st[0])>1:
		ans+=(int(st[0])-1)*get(len(st)-1,zero-1)

	a1 = solve(st[1:],zero-1)

	return ans+a1
#print solve(2345,3)+1,"ber"
for _ in range(input()):
	l,r=[int(x) for x in raw_input().split()]
	#print solve(r,3),solve(l-1,3)
	print int(solve(r,3)-solve(l-1,3))