AJJak-T002: Tiling-02

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

typedef long long lli;

const int N = 30 + 5;

lli dp1[N], dp2[N];

int main(){

    int Q;
    scanf("%d", &Q);
    dp1[0] = 1;
    dp2[1] = 1;
    for(int i = 2; i <= 30; ++i){
        dp1[i] = dp1[i - 2] + 2 * dp2[i - 1];
        dp2[i] = dp1[i - 1] + dp2[i - 2];
    }
    while(Q--){
        int n;
        scanf("%d", &n);
        cout << dp1[n] << '\n';
    }

    return 0;
}