#include<iostream> using namespace std; int ans[1000005]; long long int a(int i) { if(i==1) { ans[1] = 1; } if(i==2) { ans[2] = 2; } if(ans[i] != 0){ return ans[i]; } ans[i] = (2*a(i-1)+a(i-2))%32767; return ans[i]; } int main() { int n, k; cin>>n; while(n--){ cin >> k; cout<<a(k)%32767 << endl; } return 0; }