codeforces 55D. Beautiful numbers

D. Beautiful numbers time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output

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 l_i and r_i (1 ≤ l_i ≤ r_i ≤ 9 ·10¹⁸).

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 l_i to r_i, inclusively).

Examples Input 1 1 9 Output 9 Input 1 12 15 Output 2 题意：问你在l r之间有多少个数满足可以被各位数整除 一个数n如果满足条件，那么n一定是各位数的最小公倍数的倍数。可以尝试开出dp[20][2520][2520]表示位数为i且当前数对2520取摸为j且lcm为k的数量，但是这样 肯定是超内存的，然而事实上1至9的lcm只有48个，且都呈倍数关系，所以可以将他们都离散化吗，这样第三维缩小至48。 dfs(len,num,lcm,flag) 四个变量表示到len位数，第len位之前的数，第len位之前各位数的lcm，该位是否有限制。 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define ll long long const int INF = 2520; ll dp[25][2525][50], f[25], val[3005]; ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a%b); } ll lcm(ll a, ll b) { return a / gcd(a, b)*b; } ll dfs(ll len, ll num, ll LCM, ll flag) { if (len < 0) return num%LCM == 0; if (!flag&&dp[len][num][val[LCM]] != -1) return dp[len][num][val[LCM]]; int k = flag ? f[len] : 9; ll ans = 0; for (int i = 0;i <= k;i++) { ll nowlcm = LCM; ll nownum = (num * 10 + i) % INF; if (i > 0) nowlcm = lcm(nowlcm, i); ans += dfs(len - 1, nownum, nowlcm, flag&&i == k); } if (!flag) dp[len][num][val[LCM]] = ans; return ans; } ll solve(ll n) { int len = 0; while (n) { f[len++] = n % 10; n /= 10; } return dfs(len - 1, 0, 1, 1); } int main() { ll a, b, cnt = 0; int i, j, k, sum, t; for (i = 1;i <= INF;i++) if (INF%i == 0) val[i] = cnt++; memset(dp, -1, sizeof(dp)); scanf("%d", &t); while (t--) { scanf("%lld%lld", &a, &b); printf("%lld\n", solve(b) - solve(a - 1)); } return 0; }