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