Description

The Pell sequence $a_1, a_2, a_3, \dots$ is defined as follows: $a_1 = 1$, $a_2 = 2$, and $a_n = 2a_{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 consists of a single line containing a positive integer $k$ ($1 \leq k < 1,000,000$).

Output Format

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

2
1
8

1
408