#include<bits/stdc++.h>
using namespace std;

#define endl "\n";

int br(int n, int m){
    if(n<=1 || m<=1){
        return max(n, m);
    }
    return br(n-2, m)*2-br(n-2, m-2);
}

int main(){
    freopen("figures.in", "r", stdin);
    freopen("figures.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    long long n;
    cin>>n;
    for(long long i = 0; i < n; i++){
        long long t;
        cin>>t;
        cout<<br(t, t)<<endl;
    }
    
    return 0;
}