#include<bits/stdc++.h> using namespace std; int p[1000001]; int pell(int k){ if (k==1){ return 1; } if (k==2){ return 2; } else if (p[k]==0){ p[k]=(pell(k-1)*2+pell(k-2))%32767; } return p[k]; } int t,k; int main(){ cin>>t; while(t--){ cin>>k; cout<<pell(k)<<endl; } return 0; }