P15865 [MX-X26-T1] "Cfz Round 7" feel my soul

Surely everyone has been searching all the time. / 想必每个人都在不停地寻找着。 It is not a coincidence, and it is by no means a fake love. / 那并非偶然，也绝非虚假的爱。

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.

**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$.

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

### 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