/*
 * PellSequence.cpp
 *
 *  Created on: 2013-09-08 16:46
 *  	Author: lg
 * Description: a1 = 1, a2 = 2, ... , an = 2 * an ? 1 + an - 2 (n > 2)
 *              ans = an % 32767
 */
#include <stdio.h>

int PellMod(int);

int main()
{
    int tc, n;
    scanf("%d", &tc);
    while(tc--){
        scanf("%d", &n);
        printf("%d\n", PellMod(n));
    }
    return 0;
}

int PellMod(int n)
{
    if(n == 1) return 1;
    int ans[2] = {1, 2}, j = 0;
    for(int i = 2; i < n; j = 1 - j, i++){
        ans[j] += 2 * ans[1 - j];
        ans[j] %= 32767;
    }
    return ans[1 - j];
}

  

Pell Sequence