#include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 long long int dp[][];

 void init()

 {

         dp[][]=;dp[][]=;dp[][]=;

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

             {

                dp[i][]=dp[i-][]*-dp[i-][];//dp[i][0]表示长度为i的不含49的数的个数

                dp[i][]=dp[i-][];//dp[i][1]表示长度为i的不含49且最高位为9的数的个数

                dp[i][]=dp[i-][]*+dp[i-][];// dp[i][2]表示长度为i的含49 的数的个数

             }

 }

 int bit[];

 long long int solve(long long int n)

 {

   int len=;

   while(n)

   {

     bit[len++]=n%;

     n/=;

   }

   bit[len]=;

   long long int ans=;

   bool flag=;

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

   {

        ans+=dp[i-][]*bit[i];

        if(flag) ans+=dp[i-][]*bit[i];//如果高位已经出现49那么后面随意

        if(flag== && bit[i]>) ans+=dp[i-][];

        if(bit[i+]== && bit[i]== ) flag=;

   }

   if(flag ) ans++;

   return ans;

 }

 int main()

 {

    int t;

    long long int n;

    scanf("%d",&t);

    init();

    while(t--)

    {

         scanf("%I64d",&n);

         cout<<solve(n)<<endl;

    }

    return ;

 }