#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--){ int k; cin>>k; cout<<a[k]<<endl; } return 0; }