Untitled

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define X first
#define Y second

const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1};
const int dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
const double EPS = 1e-8;
const int mod = 998244353; // 1e9+7, 998244353
const int phi = 1e9+6; // 1e9+7, 998244353
// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

int n;
ll dp[30][30][2][3];
ll go(int bt = 29, int cnt = 0, int ls = 0, int lit = 2) {
    if (bt == -1) return cnt;
    auto &ret = dp[bt][cnt][ls][lit];
    if (~ret) return ret;
    ret = 0;
    if (ls) {
        ret+=go(bt-1, cnt, ls, lit); // off
        if ((bt&1) == lit || lit == 2) ret+=go(bt-1, cnt+1, ls, bt&1); // on
        else ret+=go(bt-1, cnt, ls, lit); // on but it does not count
    }
    else {
        if (n>>bt&1) {
            ret+=go(bt-1, cnt, 1, lit); // off
            if (lit == 2 || (bt&1) == lit) ret+=go(bt-1, cnt+1, ls, bt&1); // on
            else ret+=go(bt-1, cnt, ls, lit); // on but it does not count
        }
        else ret+=go(bt-1, cnt, ls, lit); // off
    }
    return ret;
}

void burn(int tc) {
    cin >> n;
    memset(dp, -1, sizeof dp);
    cout << go();
}

int main()
{
    AboTaha_on_da_code

    // freopen("cheat.in", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int T = 1; cin >> T;

    for (int i = 1; i <= T; i++) {
        //        cout << "Case " << i << ": ";
        burn(i);
        cout << '\n';
    }
    return (0-0);
}