#include <bits/stdc++.h> using namespace std; int a[1000005]; int main() { int n,t; a[1]=1,a[2]=2; cin>>t; for(int i=3;i<=1000000;i++) { a[i]=a[i-1]*2+a[i-2]; a[i]=a[i]%32767; } while(t--) { cin>>n; printf("%lld\n",a[n]); } }