#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <cstring>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
int a[N], k, n;
signed main(void){
	a[1]=1;
	a[2]=2;
	cin >> n;
	for (int i=3; i<=N; i++){
		a[i]=( 2 * a[i-1]+a[i-2])%32767;
	}
	while(n--){
		cin >> k;
		cout << a[k] << endl;
	}
    return 0;
}

#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int f(int n)
{
	if(a[n])
		return a[n];
	a[n]=(f(n-1)*2+f(n-2))%32767;
	return a[n];
}
int main()
{
	int n;
	cin >>n;
	a[1]=1,a[2]=2;
	while(n--)
	{
		int num;
		cin >> num;
		cout << f(num)<<endl;
	}
}