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:
"""
#If FastIO not needed, used this and don't forget to strip
#import sys, math
#input = sys.stdin.readline
"""

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


"""
Suppose the number is 

00000000067890112343

dp[i][j] = number of length i numbers with j 0s, including 0

How to calculate the number <= R

Len = Len(str(R))
dp[Len-1][3]
+ (dig1-1)*dp[Len-1][2]
+ (dig2-1)*dp[Len-2][1]
+ (dig3-1)*dp[Len-3][0]

2568

1000 up to 3
500 up to 2
60 up to 1


2468

0 dp[3][3]
1 dp[3][2]

2 followed by 2 digits up to 468
= 0 dp[2][2]
 1-3 dp[2][1]
 
24 followed by 1 digit up to 68
= 0 dp[1][1]
1-5 dp[1][0]
"""

def solve():
    #Digit by digit, what are our options?
    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)
                #print(dp[lenS-i-1][3-count])
                #print(dp[lenS-i-1][3-count-1]*(S[i]-1))
            if count == 2: break
            #print(res)
        return res
    for _ in range(getInt()):
        L, R = getInts()
        print(calc(R)-calc(L-1))
    return 
    
solve()