Description

The Pell sequence $a\_1, a\_2, a\_3, \dots$ is defined as follows: $a\_1 = 1$, $a\_2 = 2$, $\dots$, $a\_n = 2 a\_{n−1} + a\_{n-2}$ (for $n > 2$). Given a positive integer $k$, find the value of the $k$-th term in the Pell sequence modulo $32767$.

Input Format

The first line contains the number of test cases $n$, followed by $n$ lines of input. Each test case occupies one line and consists of a positive integer $k$ ($1 \leq k < 1000000$).

Output Format

Output $n$ lines, each corresponding to an input. Each output should be a non-negative integer.

2
1
8

1
408