Description

A lucky number is a number whose decimal representation contains only the digits \(4\) and \(7\). An almost lucky number is a number that is divisible by a lucky number. For example, \(14\), \(36\) and \(747\) are almost lucky, but \(2\) and \(17\) are not. Note that a number can be both lucky and almost lucky at the same time (for example, \(747\)).

You are given long longs a and b. Return the number of almost lucky numbers between \(a\) and$ \(b\) ,inclusive.

Input

Multiple test cases.

Each test cases is two number \(a\),\(b\) in a line seperated by a space.

\(a\) will be between \(1\) and \(10^{10}\), inclusive.

\(b\) will be between \(a\) and \(10^{10}\), inclusive.

Output

For each test case, output the answer in a single line.

Sample Input

1 10

14 14

1 100

1234 4321

Sample Output

3

1

39

1178

首先不难想到\([1,10^{10}]\)内的lucky number不多，我们可以枚举出来，且可以去除包含关系(即若\(a \mid b\)，\(b\)就没有存在的必要了)。这样算下来本质上有用的lucky number个数\(N\)只是\(O(10^3)\)级别。

首先答案每次区间可减性，即\([a,b]\)的答案为\([1,b]\)的答案减去\([1,a-1]\)答案。对于区间\([1,n]\)，我们显然可以用\(2^N\)的容斥原理。但是\(N\)太大，看上去\(2^N\)会TLE。但是由于LCM变化太大，当LCM比\(n\)大时候break复杂度就在期望的范围内了。但是可能需要卡卡常数（我懒得卡了）。

#include<cstdio>

#include<cstdlib>

using namespace std;

typedef long long ll;

#define maxn (10010)

ll A,B,lucky[maxn]; int tot,N; bool exist[maxn];

inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }

inline void dfs(ll num,int logten)

{

	if (logten > 10) return;

	if (logten) lucky[++tot] = num;

	dfs(num*10LL+4LL,logten+1); dfs(num*10LL+7LL,logten+1);

}

inline void DFS(ll range,ll &res,ll lcm,int now,int f)

{

	if (now > N) { if (lcm > 1) res += (range/lcm)*f; return; }

	DFS(range,res,lcm,now+1,f);

	ll d = gcd(lcm,lucky[now]);

	if (lcm <= (range*d+lucky[now])/lucky[now]&&lcm/d*lucky[now]<=range)

		DFS(range,res,lcm/d*lucky[now],now+1,-f);

}

inline ll calc(ll range)

{

	ll ret = 0;

	DFS(range,ret,1,1,-1);

	return ret;

}

int main()

{

	freopen("3502.in","r",stdin);

	freopen("3502.out","w",stdout);

	dfs(0,0);

	for (int i = 1;i <= tot;++i)

		for (int j = 1;j <= tot;++j)

		{

			if (i == j) continue;

			if (!(lucky[i] % lucky[j])) exist[i] = true;

		}

	for (int i = 1;i <= tot;++i) if (!exist[i]) lucky[++N] = lucky[i];

	while (scanf("%lld %lld",&A,&B) != EOF) printf("%lld\n",calc(B)-calc(A-1));

	fclose(stdin); fclose(stdout);

	return 0;

}