#include<bits/stdc++.h> using namespace std; int main() { long long p[10000001]={0,1,2},n,k; cin>>n; for(int l=0;l<n;l++){ 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; }