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