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:
import sys, math
from sys import stdin, stdout
rem = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 6+5)
#from resource import *; setrlimit(RLIMIT_STACK, (RLIM_INFINITY, RLIM_INFINITY))
take = lambda: map(int, stdin.readline().split())

def help(index,flag,arr,till):
    if index<0:
        if till<=3:
            return 1
        return 0
    if dp[index][flag][till]!=-1:
        return dp[index][flag][till]
    now=0
    if flag==0:
        for i in range(10):
            if i!=0:
                now+=help(index-1,0,arr,till+1)
            else:
                now += help(index - 1, 0, arr, till )

    else:
        p=arr[index]
        for i in range(p):
            if i!=0:
                now+=help(index-1,0,arr,till+1)
            else:
                now += help(index - 1, 0, arr, till)
        if p==0:
            now+=help(index-1,1,arr,till)
        else:
            now+=help(index-1,1,arr,till+1)
    dp[index][flag][till]=now
    return now
def solve(a):
    new=list(str(a))
    arr=[]
    for i in new:
        arr.append(int(i))
    arr.reverse()
    #print arr
    return help(len(arr)-1,1,arr,0)


q=input()
for i in range(q):
    a,b=take()
    dp=[[[-1 for i in range(20)] for j in range(2)] for k in range(20)]
    x=solve(b)
    dp = [[[-1 for i in range(20)] for j in range(2)] for k in range(20)]
    y = solve(a-1)
    print x-y