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).
# LUOGU_RID: 128943179
import sys
input = sys.stdin.readline
from functools import *
t = int(input())
for _ in range(t):
    l, r = map(int,input().split())
    s1 = str(l)
    s2 = str(r)
    s1 = '0' * (len(s2) - len(s1)) + s1
    n = len(s2)
    @lru_cache(maxsize = None)
    def f(i, up_limit, down_limit, is_num, num, t):
        if i == n:
            #print('ni', num, t)
            return int(t % num == 0) if is_num else 0
        res = 0
        up = int(s2[i]) if up_limit else 9
        down = int(s1[i]) if down_limit or not is_num else 0
        for d in range(down, up + 1):
            p = num
            if d == 2:
                if p % 2 != 0:
                    p *= 2
            if d == 3:
                if p % 3 != 0:
                    p *= 3
            if d == 4:
                if p % 4 != 0:
                    if p % 2 == 0:
                        p *= 2
                    else:
                        p *= 4
            if d == 5:
                if p % 5 != 0:
                    p *= 5
            if d == 6:
                if p % 6 != 0:
                    if p % 3 == 0:
                        p *= 2
                    elif p % 2 == 0:
                        p *= 3
                    else:
                        p *= 6
            if d == 7:
                if p % 7 != 0:
                    p *= 7
            if d == 8:
                if p % 8 != 0:
                    if p % 4 == 0:
                        p *= 2
                    elif p % 2 == 0:
                        p *= 4
                    else:
                        p *= 8
            if d == 9:
                if p % 9 != 0:
                    if p % 3 == 0:
                        p *= 3
                    else:
                        p *= 9                                            
            res += f(i + 1, up_limit and (up == d), down_limit and (down == d), is_num or d > 0, p, t * 10 + d)
        return res
    print(f(0, True, True, False, 1, 0))    