#include<bits/stdc++.h>
using namespace std;
int pell[int(2e6)] = {0,1, 2, 5};
int main() {
for (int i = 3; i <=int(1e6); i++) {
//TODO
pell[i] = (pell[i-1]*2+pell[i-2])%32767;
}
int n;
cin >> n;
for(int i=1;i<=n;i++){
int k;
cin>>k;
cout<<pell[k]<<endl;
}
return 0;
}