きっと誰もが　ずっと探しているの　/　Surely everyone is searching for it forever

それは偶然ではなくて　偽りの愛なんかじゃなくて　/　It is not a coincidence, nor is it a fake love

Yuki has a circular paper strip with $n$ cells, numbered $1$ to $n$ in order.

Yuki intends to color each cell either pink or blue. Yuki calls a coloring scheme "fishy" if and only if:

• For all pink cells, the sum of the number of blue cells adjacent to the left and right of each pink cell is equal.
• For all blue cells, the sum of the number of pink cells adjacent to the left and right of each blue cell is equal.

You need to find the number of "fishy" coloring schemes. Two coloring schemes are considered different if and only if there exists a positive integer $i \le n$ such that cell $i$ is colored differently in the two schemes.

Input

The first line of the input contains two integers $c$ and $t$, representing the subtask number and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case consists of a single line containing an integer $n$.

Output

For each test case, output a single line containing an integer representing the number of "fishy" coloring schemes.

Examples

Input 1

0 8
2
3
5
8
12
40
98
138

Output 1

4
8
2
8
14
8
4
10

Note 1

For the first test case, the "fishy" coloring schemes are: pink-pink, blue-blue, pink-blue, and blue-pink.

For the second test case, the "fishy" coloring schemes are: pink-pink-pink, pink-pink-blue, pink-blue-pink, blue-pink-pink, pink-blue-blue, blue-pink-blue, blue-blue-pink, and blue-blue-blue.

For the third test case, the only "fishy" coloring schemes are all-pink and all-blue.

Constraints

For all test cases:

• $1 \le t \le 5\cdot 10^5$
• $1 \le n \le 10^9$

This problem uses bundled testing.

• Subtask 1 (12 points): $t \le 12$, $n \le 12$.
• Subtask 2 (32 points): $n$ is guaranteed to be a prime number.
• Subtask 3 (36 points): $n$ is guaranteed to be an odd number.
• Subtask 4 (20 points): No additional constraints.