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