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