#include <stdio.h>

int b[1000];
int fib[100];

void precalcfib() {
	int i, t, a=1, b=1;
	fib[0] = fib[1] = 1;
	for (i=0; i<30; i++) {
		t = a;
		a+=b;
		b=t;
		fib[2+i]=a;
	}
}

void calcfib(int x) {
	int i, start;
	for (i=0; i<30; i++) b[i]=0;
	for (start=29; start>=0; start--) {
		if (x>=fib[start]) break;
	}
	for (i=start; i>=0; i--) {
	//	printf("Schleife, i=%d, fib[i]=%d, x=%d\n", i,fib[i], x);
		if (x>=fib[i]) {
			x-=fib[i];
			b[i]=1;
			i--;
		}
	}
//	for (i=0; i<20; i++) printf("%d ", b[i]);
//	printf("\n");
}
void calckm() {
	
	int sum = 0;
	int i;
	for (i=2; i<30; i++) sum += b[i]*fib[i-1];
	printf("%d\n", sum);
}

int main() {
	freopen("convert.in", "r", stdin);
	int t, x;
	precalcfib();
//	calcfib(42);
//	return 0;
	for (scanf("%d", &t); t>0; t--) {
		scanf("%d", &x);
		calcfib(x);
		calckm();
	}	
	return 0;
}