#include<iostream> using namespace std; int main(){ int b,c,k[1001],max=0; long long a[10000]; cin>>c; for(int i=0;i<c;i++){ cin>>k[i]; if(max<k[i]){ max=k[i]; } } a[1]=1; a[2]=2; for(int i=3;i<=max;i++){ a[i]=a[i-1]*2%32767+a[i-2]%32767; } for(int i=0;i<c;i++){ cout<<a[k[i]]<<endl; } }