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