#include<bits/stdc++.h> 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,g; cin>>n; for(int i=1;i<=n;++i){ cin>>g; cout<<pell(g)%32767<<endl; } return 0; }