codeforces 55D

maksyuki 发表于 oj 分类,标签:
0

Beautiful numbers

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.

Input

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 li and ri (1 ≤ li ≤ ri ≤ 9 ·1018).

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

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).

Sample test(s)

input

1
1 9

output

9

input

1
12 15

output

2

 

题目类型:数位DP

算法分析:dp[pos][mod][lcm]表示前pos位数除以前pos位数的最小公倍数lcm余数为mod时的个数,由于1~9的最小公倍数为2520,所以mod每次可以直接对2520取模,由于1~2520中满足是最小公倍数的个数才48个,所以可以使用一个映射将最后一维的空间从2520优化到48