Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

 

Sample Input

 

Sample Output

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,x,n) for(int i=(x); i<=(n); i++)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e18;

const int maxm = 1e6 + ;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

int dir[][] = {{,},{,-},{-,},{,}};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

const int mod = ;

#define inf 0x3f3f3f3f

#define ll long long

const int maxn = ;

int dp[][];

int a[];

int dfs(int pos,int pre,int sta,bool limit)

{

    if(pos==-) return ;

    if(!limit && dp[pos][sta]!=-) return dp[pos][sta];

    int up=limit?a[pos]:;

    int cnt=;

    for(int i=;i<=up;i++)

    {

        if(pre== && i==) continue;

        if(i==) continue;

        cnt += dfs(pos-,i,i==,limit&&i==a[pos]);

    }

    if(!limit) dp[pos][sta]=cnt;

    return cnt;

}

int solve(int x)

{

    int pos=; //记录有多少个数位

    while(x)

    {

        a[pos++]=x%;

        x/=;

    }

    return dfs(pos-,-,,true); //从最高位开始枚举，pre位是-1，sta是0，limit是true

    //dfs(int pos,int pre,int sta,bool limit)

}

int main()

{

    int t;

    int n,m;

    while(~scanf("%d%d",&n,&m),n+m)

    {

        ms(dp,-);

        printf("%d\n",solve(m)-solve(n-));

    }

}

/*

【题意】

数位上不能有4也不能有连续的62.给定区间共有多少合法的数。

【类型】

数位DP入门

【分析】

没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了

所以这个约束没有记忆化的必要，而对于62的话涉及到两位，

当前一位是6或者不是6这两种不同情况我计数是不相同的，

所以要用状态来记录不同的方案数。

dp[pos][sta]表示当前第pos位，前一位是否是6的状态，

这里sta只需要去0和1两种状态就可以了，

不是6的情况可视为同种，不会影响计数。

【时间复杂度&&优化】

【trick】

【数据】

*/