#include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include<iomanip> using namespace std; int b[1000000],n,m,ans=0; int main(){ b[1]=1; b[2]=2; cin>>m; for(int i=3;i<=1000000;i++){ b[i]=2*b[i-1]+b[i-2]; b[i]%=32767; } while(m--){ cin>>n; cout<<b[n]<<endl; } return 0; }