Pell Sequence

Problem Background

Special for beginners, ^_^

Problem Description

The Pell sequence $a_1, a_2, a_3, \dots$ is defined as follows: $a_1 = 1, a_2 = 2, \dots, a_n = 2a_{n-1} + a_{n-2} \; (n > 2)$.

Given a positive integer $k$, find the value of the $k$-th term of the Pell sequence modulo $32767$.

Input Format

The first line is the number of test cases $n\; (1 \le n \le 10^3)$, followed by $n$ lines of input. Each test case occupies one line and contains a positive integer $k\; (1 \le k < 1000)$.

Output Format

$n$ lines, each line outputs the result corresponding to one input. The output should be a non-negative integer.

Sample Input

2
1
8

Sample Output

1
408

Constraints

Time limit: 1s, memory limit: 1024KiB for each test case.