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