#include <stdio.h>
#include <vector>
using namespace std;

vector<long> fibs;

long fib(int n) {
	if(n < fibs.size()) return fibs[n];
	for(int i = fibs.size(); i <= n; ++i) {
		fibs.push_back(fibs[i-1] + fibs[i-2]);
	}
	return fibs[n];
}

int main() {
	int t, x, b;
	vector<int> z;

	fibs.push_back(1); fibs.push_back(1); fibs.push_back(2); fibs.push_back(3);

	freopen("convert.in", "r", stdin);
	for(scanf("%i", &t); t>0; --t) {
		scanf("%i", &x);

		b = 1;
		while(fib(b) < x) ++b;
		//printf("#%i \n", b);

		z.clear();
		while(b >= 1) {
			if(x >= fib(b)) { z.push_back(1); x -= fib(b); }
			else z.push_back(0);
			//printf("%i", z.back());
			--b;
		}

		long r = 0;
		for(int i = 0; i < z.size()-2; ++i) {
			//printf("%i: %i * %li\n", i, z[z.size()-i-2], fib(i+1));
			r += fib(i+1)*z[z.size()-i-2];
		}
		printf("%li\n", r);
	}
	return 0;
}