1

# include<iostream>
# include<cstring>
using namespace std;
int main(){
   int n,i,j;
   cin>>n;
   int k,b[n],a[1000]={0,1,2};
   for (i=1;i<=n;i++){
       cin>>k;
       for (j=3;j<=k;j++){
           a[j]=2*a[j-1]%32767+a[j-2]%32767;
       }
       cout<<a[k]<<endl;
   }
   return 0;
}