Python :

# coding=utf-8
def matrix_mult(A, B, mod):
    # 矩阵乘法，并对结果取mod
    return [
        [(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod, (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod],
        [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod, (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod]
    ]

def matrix_pow(matrix, n, mod):
    # 矩阵快速幂
    result = [[1, 0], [0, 1]]  # 初始化为单位矩阵
    base = matrix
    
    while n > 0:
        if n % 2 == 1:
            result = matrix_mult(result, base, mod)
        base = matrix_mult(base, base, mod)
        n //= 2
    
    return result

def pell_number(k, mod):
    if k == 1:
        return 1
    elif k == 2:
        return 2
    
    # 初始化矩阵和向量
    matrix = [[2, 1], [1, 0]]
    vector = [2, 1]
    
    # 计算矩阵的k-2次幂
    result_matrix = matrix_pow(matrix, k - 2, mod)
    
    # 计算最终结果
    a_k = (result_matrix[0][0] * vector[0] + result_matrix[0][1] * vector[1]) % mod
    
    return a_k

# 读取输入
n = int(input())
k_values = [int(input()) for _ in range(n)]

# 计算并输出结果
results = [pell_number(k, 32767) for k in k_values]
for result in results:
    print(result)