Background

Surely everyone has been searching all the time. / 想必每个人都在不停地寻找着。

It is not a coincidence, and it is by no means a fake love. / 那并非偶然，也绝非虚假的爱。

Problem Description

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

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

• For all pink cells, the total number of adjacent blue cells on the left and right of each pink cell is the same.
• For all blue cells, the total number of adjacent pink cells on the left and right of each blue cell is the same.

You need to compute the number of "Yuyu" coloring schemes. Two coloring schemes are considered different if and only if there exists a positive integer $i \le n$ such that cell $i$ has different colors in the two schemes.

Input Format

This problem has multiple test cases.

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

Then the test cases follow. For each test case, there is one line containing one integer $n$.

Output Format

For each test case, output one line containing one integer, the number of "Yuyu" coloring schemes.

0 8
2
3
5
8
12
40
98
138

4
8
2
8
14
8
4
10

Hint

Sample 1 Explanation

For the $1$-st test case, the "Yuyu" colorings are pink-pink, blue-blue, pink-blue, and blue-pink.

For the $2$-nd test case, the "Yuyu" colorings 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 $3$-rd test case, the only "Yuyu" colorings 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 tests.

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

Translated by ChatGPT 5