#include <iostream>

using namespace std;

int main()
{
    int t,n;
    int T[101]={0};
    cin >> t;

    for(int i=1; i<=t; i++)
    {
        cin >> n;
        T[0] = 4;
        T[1] = 7;
        for (int i=2; i<=n; i++)
        {
            T[i] = 2*(T[i-1]) + 5*(T[i-2]);
        }

        for (int k=n; k<=n; k++)
        {
            cout << T[n]%2011 << endl;
        }
    }
    return 0;

}