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