#P9022. [2017年备战省选]jzpext

    ID: 9228 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高数位 DP最小公倍数非受限状态记忆化上界限制状态同余的加减乘运算预计算转移

[2017年备战省选]jzpext

Description

我们称一个正整数n是好的,当且仅当n能被他的所有数位整除。 现在需要计算在一个给定的区间[l, r]中的好数的个数。

Format

Input

第一行,询问数t。

下面t行,每行两个数l, r,表示询问的区间。

Output

对于每个询问输出一行表示答案。

Samples

1
1 100
33

Hint

30%的数据 r<=10^7

另30%的数据 t<=100

100%的数据 t<=2.5*10^4, 1<=l<=r<=10^18