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