import java.io.File;
import java.util.Scanner;


public class convert {
	public static void main(String [] args) throws Exception
	{
		Scanner x = new Scanner(new File("convert.in"));
		
		int N = Integer.parseInt(x.next());
		
		int fibo[] = new int[25];
		
		fibo[0] = 1;
		fibo[1] = 2;
		
		for(int i=2; i<25; i++)
		{
			fibo[i] = fibo[i-1]+fibo[i-2];
		}
		
		while(N>0)
		{
			int kilometres = Integer.parseInt(x.next());
			String zahl="";
			
			for(int j=24; j>=0; j--) {
				while(j>=0 && kilometres<fibo[j]) {
					zahl = zahl.concat("0");
					j--;
				}
				
				if(j>=0)
				{
					zahl = zahl.concat("1");
					kilometres-=fibo[j];
					if(j>0) {
					zahl = zahl.concat("0");
					j--; }
				}
			}
			
			String converted = zahl.substring(0, zahl.length()-1);
			/*System.out.println(zahl);
			System.out.println(converted);*/
			
			int  erg=0;
			for(int j=converted.length()-1, i=0; j>=0; j--, i++)
			{
				erg+=Integer.parseInt(converted.charAt(j)+"")*fibo[i];
			}
			System.out.println(erg);
			
			N--;
			
			
		}
		
	}
}