#include <stdio.h>
#include <iostream>
#include <map>
#include <assert.h>

using namespace std;

const int CALC = 1000*1000*10;
long long mas[CALC + 10] = { 0 };

map<long long, long long> cache;

long long f (long long n)
{
	if (n <= CALC)
	{
		return mas[n];
	}

	map<long long, long long>::iterator value = cache.find(n);
	long long result;
	if (value == cache.end())	
	{
		result = f(n/2) + f(n - n/2);
		cache[n] = result;
	}
	else
	{
		result = value->second;
	}
	
	return result;	
}

int main()
{
	freopen("legion.in", "r", stdin);
	//freopen("legion.out", "w", stdout);

	mas[3]=1;
	for(int i=4; i<=CALC; i++)
	{
		mas[i] = mas[i/2] + mas[i-i/2];
	}
	
	int test;
	cin >> test;

	for(int i=0; i<test; i++)
	{
		long long n;

		cin >> n;
		
		assert(0 <= n && n <=1000000000000000000L);

		long long result = f(n);

		cout << result << endl;
	}

	return 0;
}
