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:
#fonciton qui retourne le nombre des chiffres classy inferieur a une borne    
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))