#P3765. 神奇的数

    ID: 2967 传统题 1000ms 512MiB 尝试: 67 已通过: 9 难度: 6 上传者: 标签>CF2000提高数位 DP最小公倍数上界限制状态非受限状态记忆化预计算转移

神奇的数

题目描述

我们认为任何数都可以被 00 整除。现在给你 TT 个区间,请你求出 [l,r][l,r] 中能被自身的每一位整除的数的个数。

输入格式

第一行输入一个 TT,代表测试组数。

从第二行到第 T+1T+1 行,每行一组测试,输入 l,rl,r,表示查询区间 [l,r][l,r] 之间可以被自己的每一位数字整除的数的个数。

输出格式

每行输出一个答案。

1
1 10
10

样例说明

注意,1010 可以被第二位 11 整除,也可以被第一位 00 整除,所以 1010 也是题目所要求的数。

数据规模与约定

对于 100%100\% 的数据,1≤l≤r≤9×10181 \le l \le r \le 9 \times 10^{18},T≤10T \le 10。

此题存在版权,故原 BZOJ 不再支持提交,保留在此只供大家参考题面! 望见谅!