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:
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  # осталось знаков после i

        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:
#        out=out+1+int(s[n-2])
        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)