P11003 [Lanqiao Cup 2024 NOI Qualifier Python B] The Truth of Lanqiao Village

In the scenic Lanqiao Village, $n$ villagers sit around an old round table and take part in a battle of ideas. Each villager has a clear identity: either an honest person who always tells the truth, or a hopeless liar who always lies. When the meeting begins, a debate about truth and falsehood starts. Each villager speaks in turn. Villager $i$ makes the following claim: among the next two villagers after him—namely, villager $i + 1$ and villager $i + 2$ (note that the numbering is circular, so if $i$ is the last one, then $i + 1$ is the first one, and so on)—one is telling the truth and the other is lying. Among all these uncertain statements, how many true words are hidden behind the veil of lies? Please explore every possible arrangement of truth and falsehood, and compute, over all possible truth/lie arrangements, the total number of liars.

The first line contains an integer $T$, indicating that each input contains $T$ test cases. Then $T$ test cases follow. Each test case consists of one line containing an integer $n$, representing the number of villagers.

Output $T$ lines. Each line contains an integer, representing the answer for each test case in order.

For $10\%$ of the test cases, $T = 1$, $3 \le n \le 10$. For $40\%$ of the test cases, $1 \le T \le 10^2$, $3 \le n \le 3 \times 10^3$. For all test cases, $1 \le T \le 10^5$, $3 \le n \le 10^{18}$. #### Sample Explanation In the sample, the possible arrangements are “false, false, false”, “true, true, false”, “true, false, true”, “false, true, true”. The total number of liars is $3 + 1 + 1 + 1 = 6$. Translated by ChatGPT 5