#include<bits/stdc++.h> using namespace std; int main(){ long long n,k,pell[100001]={0,1,2}; cin>>n; for(int i=0;i<n;i++){ cin>>k; for(int j=3;j<=k;j++){ a[j]=(2*a[j-1]+a[j-2])%32767; } cout<<pell[k]<<endl; } return 0; }