#include <stdio.h>

#define MOD_NUM 1000000007

void input(void);
void solve(void);
long long solving(int fromLeftStartPos, int fromRightStartPos, int isSymmetry);

long long cache[105][105][2];
int N;

int main(void)
{
    int tc, T;
    freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    for (tc = 1; tc <= T; tc++)
    {
        input();
        solve();
    }

    return 0;
}

void input(void)
{
    scanf("%d", &N);
}

void solve(void)
{
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++)
            for (int k = 0; k < 2; k++)
                cache[i][j][k] = -1;

    printf("%lld\n", solving(0, N - 1, 1));
}
//현재까지의 대칭상태가 isSymmetry 이고(1 : 대칭, 0 : 비대칭), fromLeftStartPos, fromRightStartPos 서부터 고려하여 타일을 놓는다고 가정했을 때 놓을 수 있는 가지 수
long long solving(int fromLeftStartPos, int fromRightStartPos, int isSymmetry)
{
    //기저 사례
    if (fromRightStartPos - fromLeftStartPos < -1)
        return 0;
    else if (fromRightStartPos - fromLeftStartPos == -1 || fromRightStartPos - fromLeftStartPos == 0)
    {
        if (isSymmetry == 1)    //대칭이면
            return 0;
        else
            return 1;
    }

    long long &ret = cache[fromLeftStartPos][fromRightStartPos][isSymmetry];

    if (ret != -1)
        return ret;

    ret = 0;

    ret = (solving(fromLeftStartPos + 1, fromRightStartPos - 1, isSymmetry * 1) % MOD_NUM + solving(fromLeftStartPos + 2, fromRightStartPos - 2, isSymmetry * 1) % MOD_NUM +
        solving(fromLeftStartPos + 1, fromRightStartPos - 2, isSymmetry * 0) % MOD_NUM + solving(fromLeftStartPos + 2, fromRightStartPos - 1, isSymmetry * 0) % MOD_NUM) % MOD_NUM;

    return ret;
}