#include<iostream>
#include<algorithm>
using namespace std;
const int maxn =1000000+10;
int ans[maxn];
int work(int m)
{
    if(ans[m]!=0) return ans[m];
    return ans[m]=(work(m-1)*2+work(m-2))%32767;
}
int main(void)
{
    int n;
    cin >> n;
    ans[1]=1;
    ans[2]=2;
    for(int i=0;i<n;i++)
    {
        int m;
        cin >> m;
        cout << work(m) << endl;
    }
    return 0;   
}