#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> finres;
int main() {
    cin>>n;

    finres.push_back(1);
    finres.push_back(2);
    for(int i =0;i<n;i++)
    {
      int k;
      cin>>k;
      
      if(finres.size()>k-1)
      {
          cout<<finres[k-1]<<endl;
      }
      else{
          for(int i =finres.size();i<k;i++)
          {
             int tv =2*finres[i-1]+finres[i-2];
             tv = tv%32767;
             finres.push_back(tv);
          }
          cout<<finres[k-1]<<endl;
      }
     
     
      
    }
}