难度： 红

披着数位 dp 外衣的红色题目。

我们对于每个数，检查其是否合法。

然后把前缀和求出来，也就是记 $s_i$ 为小于等于 $i$ 的合法的数的个数。

对于每一次询问，求 $a$ 至 $b$ 合法的数的个数，也就是 $s_b-s_{a-1}$。

时间复杂度 $n\log_{10}n$。

$20$ 行代码：

#include<bits/stdc++.h>
using namespace std;
int s[10000100],a,b;
inline int ck(int x){
	while(x){
		if(x%100==62) return 0;
		if(x%10==4) return 0;
		x/=10;
	}
	return 1;
}
int main(){
	for(int i=1;i<=int(1e7);i++) s[i]=ck(i);
	for(int i=1;i<=int(1e7);i++) s[i]+=s[i-1];
	while(1){
		scanf("%d%d",&a,&b);
		if(a==0&&b==0) return 0;
		printf("%d\n",s[b]-s[a-1]);
	}
}