#include<bits/stdc++.h> /*1+1=1*1+1*1=1*(1+1)=1/(1/2)=1/0.5=(2/1)=(1+1/1)=1+1 无解 !!!!!!! */ using namespace std; int main(){ long long n,k[1001]={},pell[1001]={0,1,2}; for(int i=3;i<1000;i++){ pell[i]=2*pell[i-1]+pell[i-2]; } cin>>n; for(int i=0;i<n;i++){ cin>>k[i]; } for(int i=0;i<n;i++){ cout<<pell[k[i]]%32767<<endl; } return 0; }