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