# CF55D Beautiful numbers

• 201通过
• 601提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 动态规划,动规,dp 数位动规,数位dp 状态压缩,状压
• 难度 NOI/NOI+/CTSC
• 时空限制 4000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

题目描述

Volodya是一个很皮的男♂孩。他认为一个能被它自己的每一位数上的数整除的数是很妙的。我们先忽略他的想法的正确性（如需证明请百度“神奇海螺”），只回答在l到r之间有多少个很妙的数字。

输入输出格式

输入：总共有t个询问：

第一行：t；

接下来t行：每行两个数l和r。

注意：请勿使用%lld读写长整型（虽然我也不知道为什么），请优先使用cin（或者是%I64d）。

输出：t行，每行为一个询问的答案。

## 题目描述

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_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=9·10^{18}$ ).

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).

输出格式：

Output should contain $t$ numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from $l_{i}$ to $r_{i}$ , inclusively).

## 输入输出样例

输入样例#1： 复制
1
1 9

输出样例#1： 复制
9

输入样例#2： 复制
1
12 15

输出样例#2： 复制
2

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。