#include<iostream>
using namespace std;
int main(){
	int n;
	cin
	>>n;
	while(n--){
		int k;
		cin
		>>k;
		if(k<3){
			cout
			<<k
			<<"\n";
			continue;
		}
		int a=1;
		int b=2;
		for(int i=2;i<k;i++){
			int c=a;
			a=b;
			b=(c+2*b)%32767;
		}
		cout
		<<b
		<<"\n";
	}
}

递归记忆化也不能满足，但是<入门>的递归章节里的Pell建议用递归记忆化做，可以做出来[笑脸]