#include <iostream>  

using namespace std;  

int main() {  
    int n;  
    cin >> n;  
    
    // 预处理Pell数列模32767的值  
    const int MOD = 32767;  
    const int MAX_K = 1000000;  
    int pell[MAX_K + 1];  
    
    pell[1] = 1;  
    pell[2] = 2;  
    
    for (int i = 3; i <= MAX_K; ++i) {  
        pell[i] = (2 * pell[i - 1] + pell[i - 2]) % MOD;  
    }  
    
    // 处理每组测试数据  
    for (int i = 0; i < n; ++i) {  
        int k;  
        cin >> k;  
        cout << pell[k] << endl;  
    }  
    
    return 0;  
}