/*
    題意：問n以內的數字中包含49串的個數
    數位統計
    先預處理長度為n的所有數字里
    包含49串的個數have[n]
    不包含49的個數_have[n]
    不包含49串中最高位是9的個數_9have[n]

    然后對于輸入的n，逐位統計
    用數位統計時是統計[1,n)的，所以一開始n要+1

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>

using namespace std;

const int MAXN = 100010;


long long have[30] , _have[30] , _9have[30];
int bit[30];

void init()
{
    _have[0] = 1;
    for(int i = 1; i < 20 ; i++)
    {                       //"49"
        have[i] = 10*have[i-1] + _9have[i-1];
        _have[i] = 10*_have[i-1] - _9have[i-1];
        _9have[i] = _have[i-1];
    }
}

int main()
{
    //freopen("in","r",stdin);
    init();
    int T;
    for(cin>>T ; T-- ;)
    {
        unsigned long long n , _n;
        cin>>n;
        n++;
        _n = n;
        int len = 0 , last = 0;
        while(_n)
        {
            bit[++len] = _n%10;
            _n/=10;
        }
        long long ans = 0;
        bool flag = false;
        for(int i = len ; i ; i --)
        {
            for(int j = 0; j < bit[i] ; j++)
            {
                ans += have[i-1];
                if(flag) ans += _have[i-1];
                if(flag == false && j == 4) ans += _9have[i-1];
            }
            if(last == 4 && bit[i] == 9)flag = true;
            last = bit[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}