#include <iostream> using namespace std; int a[1000005]; int n, k; int main() { cin >> n; a[1] = 1; a[2] = 2; for (int i = 3; i < 1000000; i++) { a[i] = 2 * a[i - 1] + a[i - 2]; a[i] %= 32767; } while (n--) { cin >> k; cout << a[k] << endl; } return 0; }