#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <list>
#include <map>
#include <queue>

#define mp make_pair
#define i64 long long;
#define ui64 unsigned long long;
using namespace std;

int main() {
#ifdef _KOCH
	freopen("input.txt", "r", stdin);
#else
	// freopen("search4.in", "r", stdin);
	// freopen("search4.out", "w", stdout);
#endif
	int n;
	cin >> n;

	int64_t val = 1;
	vector<int64_t> v(25);
	for (int i = 0; i < v.size(); ++i) {
		v[i] = val;
		val *= 4ll;
	}
	for (int i = 0; i < n; ++i) {
		int64_t a;
		cin >> a;
		int k = 24;
		int res = 0;
		while (a > 0) {
			int64_t x = a / v[k];
			if (x == 1) {
				res++;
			}
			if (x == 2) {
				res += 3;
			}
			if (x == 3) {
				res += 4;
			}
			a -= x*v[k];
			k--;
		}
		cout << res << endl;
	}
	return 0;
}