Background

Special for beginners, ^_^

Pell Sequence

Problem Description

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

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

Input Format

The $1$st line is the number of test cases $n$ ($1 \le n \le 100$), followed by $n$ lines of input. Each test case occupies $1$ line and contains one positive integer $k$ ($1 \le k < 1000000$).

Output Format

$n$ lines, each line corresponding to one input. Each line should contain a non-negative integer.

Sample Input

2
1
8

Sample Output

1
408

Constraints

1s, 1024KiB for each test case.