eca184bc.cpp

constexpr int U = 20;
constexpr int DIGIT = U + 5;

long long dp[DIGIT][3];
/**
 * @brief
 * dp[i][j]: the j-th status of numbers whose length equals to i
 * @status:
 * dp[i][0]: not contain 49
 * dp[i][1]: not contain 49 but begin with 9
 * dp[i][2]: contain 49
*/

int a[DIGIT];

inline void init()
{
    /**
     * @brief
     * must be called before sol::main()
    */

    dp[0][0] = 1;
    for (int i = 1; i <= U; i++)
    {
        dp[i][0] = dp[i - 1][0] * 10 - dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
        dp[i][2] = dp[i - 1][2] * 10 + dp[i - 1][1];
    }
}

namespace sol
{
    int len;

    inline void cal(long long x)
    {
        len = 0;
        while (x)
        {
            a[++len] = x % 10;
            x /= 10;
        }
        a[len + 1] = 0;
    }

    inline long long main(long long x)
    {
        cal(x);

        bool flag = 0;
        long long ans = 0;

        for (int i = len; i >= 1; i--)
        {
            ans += a[i] * dp[i - 1][2];

            if (flag)
            {
                ans += a[i] * dp[i - 1][0];
            }
            else if (a[i] > 4)
            {
                ans += dp[i - 1][1];
            }

            if (a[i + 1] == 4 && a[i] == 9)
            {
                flag = 1;
            }
        }

        if (flag)
        {
            ans++;
        }

        return ans;
    }

} // namespace sol

int T;
long long n;

int main()
{
    init();

    io::read(T);
    for (register int _ = 0; _ < T; _++)
    {
        io::read(n);
        io::writeln(sol::main(n));
    }
}