#include <bits/stdc++.h>

using namespace std;

const int N = 32767;

//递推
int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, c;
    for (int i = 3; i <= n; ++i) {
        c = (a + 2 * b) % N;
        a = b % N;
        b = c % N;
    }
    return c % N;
}

int main() {
    int n, k;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> k;
        cout << dp(k) << endl;
    }
    return 0;
}