#include <iostream>
#include <map>
#include <cassert>

using namespace std;

map<long long, long long> cache;

long long solve(long long n)
{
	if (n < 3)
		return 0;
	if (n == 3)
		return 1;

	map<long long, long long>::const_iterator it = cache.find(n);
	if (it != cache.end())
		return it->second;

	long long result = solve(n/2) + solve(n - n/2);

	cache[n] = result;
	return result;
}

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

	int testn;
	cin >> testn;
	
	for (int testi = 0; testi < testn; testi++)
	{
		long long n;
		cin >> n;
		assert(n >= 1L && n <= 1000000000000000000L);
		cout << solve(n) << endl;
	}
	
	return 0;
}