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