1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll __int64 5 using namespace std; 6  7 ll dp[30][3]; 8 int num[30]; 9 10 void inti()11 {12     memset(dp,0,sizeof(dp));13     dp[0][0]=1;14     dp[0][1]=0;15     dp[0][2]=0;16     for(int i=1; i<30; i++)17     {18         dp[i][0]=dp[i-1][0]*10-dp[i-1][1];19         dp[i][1]=dp[i-1][0];20         dp[i][2]=dp[i-1][2]*10+dp[i-1][1];21     }22 }23 24 int main()25 {26     int t;27     scanf("%d",&t);28     inti();29     while(t--)30     {31         ll n;32         scanf("%I64d",&n);33         int cnt=0;34         while(n)35         {36             num[++cnt]=n%10;37             n=n/10;38         }39         num[cnt+1]=0;40         bool flag=false;41         ll ans=0;42         for(int i=cnt; i>=1; i--)43         {44              ans+=dp[i-1][2]*num[i];45              if(flag) ans+=dp[i-1][0]*num[i];46              else if(!flag&&num[i]>4)47              {48                  ans+=dp[i-1][1];49              }50              if(num[i+1]==4&&num[i]==9)51              {52                  flag=true;53              }54         }55         if(flag) ans++;56         printf("%I64d\n",ans);57     }58     return 0;59 }