The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.
The input terminates by end of file marker.

For each test case, output an integer indicating the final points of the power.

#include<iostream>

#include<cstring>

#define LL long long

using namespace std;

LL bit[25], dp[25][2];

LL dfs(int pos, int is4, int lim)//pos当前位, is4上一位是否为4, lim上一位是否取到最大值

{

    if(pos<0) return 1;

    if(!lim && dp[pos][is4]!=-1) return dp[pos][is4];

    int las=lim?bit[pos]:9;//若上以一位没有取最大值位则可以0~9循环

    LL res=0;

    for(int i=0; i<=las; ++i)

        if(!(is4 && i==9))//搜索不含49的，结果取反

            res+=dfs(pos-1, i==4, lim&&i==las);

    if(!lim) dp[pos][is4]=res;

    return res;

}

int main()

{

    int T;

    memset(dp, -1, sizeof(dp));

    cin>>T;

    while(T--)

    {

        LL n;

        cin>>n;

        LL len=0, m=n;

        while(n)

        {

            bit[len++]=n%10;

            n/=10;

        }

        LL ans=m-dfs(len-1, 0, 1)+1;//结果取反, 且搜索过程中会包含0, 故+1

        cout<<ans<<endl;

    }

    return 0;

}

#include<iostream>

#include<cstring>

#include<cstdio>

#define LL long long

using namespace std;

LL num[25], dp[25][3];

int main()

{

    int T;

    memset(dp, 0, sizeof(dp));

    dp[0][0]=1;

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

    {

        dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//dp[i][0]表示i位数不包含49且最高位不是9的数目

        dp[i][1]=dp[i-1][0];//dp[i][1]表示i位数不包含49且最高位是9的数目
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//dp[i][2]表示i位数包含49的数目

    }

    cin>>T;

    while(T--)

    {

        LL n;

        cin>>n;

        int len=0;

        memset(num, 0, sizeof(num));

        while(n)

        {

            num[++len]=n%10;

            n/=10;

        }

        int las=0;

        bool flag=false;

        LL ans=0;

        for(int i=len; i>=1; --i)

        {

            ans+=(dp[i-1][2]*num[i]);//若n=789, 则i=3时此处计算700以内的结果

            if(flag) ans+=dp[i-1][0]*num[i];//若之前已包含49

            if(!flag && num[i]>4) ans+=dp[i-1][1];//若之前未包含49

            if(las==4 && num[i]==9) flag=true;

            las=num[i];

        }

        if(flag) ans++;

        cout<<ans<<endl;

    }

    return 0;

}