#include<iostream> // cin\cout\endl #include<cstdio> //scanf()\printf() #include<cstring> // strcpy()\strcat()\strcmp()\strlen()\memset() #include<cmath> //sqrt()\pow()\abs()\ceil()\floor()\max()\min() using namespace std; int main(){ long long n,num; cin>>n; long long pell[100000]; pell[1]=1; pell[2]=2; for(int i=0;i<n;i++){ cin>>num; for(int j=3;j<=num;j++){ pell[j]=(2*pell[j-1]+pell[j-2])%32767; } cout<<pell[num]<<endl; } return 0; }