A key insight to solving this problem is to find what makes a number not lucky

Let's try to do small numbers, trivially for 1-digit numbers, let's group them into their values mod 3

n ≡ 0 (mod 3) [0,3,6,9]

n ≡ 1 (mod 3) [1,4,7]

n ≡ 2 (mod 3) [2,5,8]

this will be useful later but for now we can see that the non-lucky 1-digit numbers are [1,2,4,5,7,8]

For 2-digit numbers, we can see that it's actually just 2 1-digit numbers, and if one of those two numbers is in [0,3,6,9], we can just take the substring containing that number making it automatically happy, you can also generalize this for any n-digit number.

but what about the numbers not containing any digits in [0,3,6,9]? let x be any number in the set [1,4,7] (x ≡ 1 (mod 3)) and let y be any number in [2,5,8] (y ≡ 2 (mod 3)). This gives is 4 numbers in the form of

1. xy
2. yx
3. xx
4. yy

Recall the divisibility rule of 3, which states that if the sum of the digits of a number is divisible by three, the number itself is also divisible by 3, let's apply this to the numbers above.

xy = 1 + 2 = 0 (mod 3)

yx = 2 + 1 = 0 (mod 3)

xx = 1 + 1 = 2 (mod 3)

yy = 2 + 2 = 1 (mod 3)

this means that only numbers in the form of xx and yy are not lucky numbers, which gives us our list of 2-digit non-lucky numbers: [11, 14, 17, 22, 25, 28, 41, 44, 47, 52, 55, 58, 71, 74, 77, 82, 85, 88]

Moving on to three digit numbers, we have

1. xxx
2. xxy
3. xyx
4. xyy
5. yxx
6. yxy
7. yyx
8. yyy

We can already eliminate those with xy and yx because we have proven that those are lucky, which leaves us with

1. xxx
2. yyy

let's solve their values

xxx = 1 + 1 + 1 = 0 (mod 3)

yyy = 2 + 2 + 2 = 0 (mod 3)

Therefore, this proves that all 3-digit numbers are lucky and subsequently all n-digit numbers (n>3) are also lucky. (because any n-digit number contains a 3-digit number)

So we have 24 non-lucky numbers

[1, 2, 4, 5, 7, 8, 11, 14, 17, 22, 25, 28, 41, 44, 47, 52, 55, 58, 71, 74, 77, 82, 85, 88]

We then just check for each number in this list if they are inside the range of x in f(x), and subtract one if true.

def f(x):
  ans = x
  non_lucky = [
    1, 2, 4, 5, 7, 8,   # one-digit non-lucky numbers
    11, 14, 17, 41, 44, 47, 71, 74, 77,   # two-digit non-lucky numbers from group xx
    22, 25, 28, 52, 55, 58, 82, 85, 88  # two-digit non-lucky numbers from group yy
  ]
  for num in non_lucky:
    if num<=x:
      ans-=1
  return ans

for testcase in range(int(input())):
  L, R = map(int,input().split())
  print(f(R)-f(L-1))