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