#include <iostream>
using namespace std;

char out[1000];
int count=0;

void binaryStrings(char *out,int n,int j){
    //Base case
    if(j==n) {
       // out[j]=NULL;
        //cout<<out<<endl;
        count++;
        return;
    }
    
    //Recursive case
    out[j]='0';
    binaryStrings(out,n,j+1);
    if(out[j-1]!='1'){
        out[j]='1';
        binaryStrings(out,n,j+1);
    }
}

int main() {
	// your code goes here
	int t;
	cin>>t;
	int n;
	while(t--){
	    count=0;
	    cin>>n;
	    binaryStrings(out,n,0);
	    cout<<count<<endl;
	}
	return 0;
}