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