#include<iostream> using namespace std; int pell(int n){ if(n<3) return n; else return 2*pell(n-1)+pell(n-2); } int main(){ int n,k; cin>>n; for(int i=0;i<n;++i){ cin>>k; cout<<pell(k)%32767; cout<<'\n'; } return 0; }