#include <iostream> #include <cmath> using namespace std; const int maxn = 1e6+5; const int mod = 32767; int a[maxn]; int main() { a[1]=1,a[2]=2; for(int i=3;i<=1e6;i++){ a[i]=(2*a[i-1]%mod+a[i-2]%mod)%mod; } int n,k; cin>>n; while(n--){ cin>>k; cout<<a[k]<<endl; } return 0; }