#include<stdio.h>

#include<string.h>

#define max 25

typedef __int64 LL;

LL dp[max][];

//dp[i][0]  不含49

//dp[i][1]  不含49但最高位为9

//dp[i][2]  含49

void init(){

    memset(dp,,sizeof(dp));

    dp[][]=;

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

        dp[i][]=dp[i-][]*-dp[i-][];

        dp[i][]=dp[i-][];

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

    }

}

LL solve(LL n){

    int bit[max],len=;

    while(n){

        bit[++len]=n%;

        n/=;

    }

    bit[len+]=;

    LL ans=;

    bool flag=false;

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

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

        if(flag){

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

        }

        else{

            if(bit[i]>){

                ans+=dp[i-][];

            }

            if(bit[i+]==&&bit[i]==){

                flag=true;

            }

        }

    }

    if(flag){

        ans++;

    }

    return ans;

}

int main(){

    init();

    int T;

    scanf("%d",&T);

    while(T--){

        LL n;

        scanf("%I64d",&n);

        printf("%I64d\n",solve(n));

    }

}

#include<stdio.h>

#include<string.h>

#define max 25

typedef long long LL;

LL dp[max][];

int bit[max],len;

LL dfs(int pos,int have,int doing){

    if(pos==){

        return have==;

    }

    if(!doing && dp[pos][have]!=-){

        return dp[pos][have];

    }

    LL ans=;

    int end=doing?bit[pos]:;

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

        int nhave=have;

        if(have==&&i!=){

            nhave=;

        }

        if(have==&&i==){

            nhave=;

        }

        if(have==&&i==){

            nhave=;

        }

        ans+=dfs(pos-,nhave,doing&&i==end);

    }

    if(!doing){

        dp[pos][have]=ans;

    }

    return ans;

}

LL solve(LL n){

    len=;

    while(n){

        bit[++len]=n%;

        n/=;

    }

    return dfs(len,,true);

}

int main(){

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

    int t;

    scanf("%d",&t);

    while(t--){

        LL n;

        scanf("%lld",&n);

        printf("%lld\n",solve(n));

    }

}