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