Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.
The first line of the input contains the number of cases *t* (1 ≤ *t* ≤ 10). Each of the next *t* lines contains two natural numbers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ 9 ·10<sup class="upper-index">18</sup>).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).
from functools import cache



def solve(s:str)->int:
    # mask说明：
    # 2 3 4 5 6 7 8 9
    # x表示不存在，数字表示除以对应数字的余数
    @cache
    def dfs( i:int , mask:str , isf0:bool , islim:bool)-> int:
        if i==len(s):
            return int(not isf0 and mask.count('x')+mask.count('0')==len(mask))
        res = 0
        if isf0:
            # 前面是前导0，继续添加前导0的情况
            res += dfs(i+1 , mask , True , False)
        # 继续添加数字的情况
        # 这一位的取值范围受isf0和islim的影响 ，lower = isf0 ? 1 : 0 , upper = islim ? s[i]-'0' : 9
        lower = 1 if isf0 else 0
        upper = int(s[i]) if islim else 9
        rest = len(s)-i-1 # 剩余的位数
        for j in range(lower , upper+1):
            num =  j*10**rest 
            mask_copy = list(mask)
            for k,c in enumerate(mask):
                if c=='x' and k+2!=j:
                    continue
                mask_copy[k] = str(((num % (k+2))+(int(c) if c!='x' else 0)) % (k+2)) # 计算加上j后的余数即mask
            res += dfs(i+1 , ''.join(mask_copy) , False , islim and j==upper)
        return res
    
    return dfs(0 , 'xxxxxxxx' , True , True)

t = int(input())
while t:
    t-=1
    l,r = map(int , input().split())
    print(solve(str(r))-solve(str(l-1)))