P11003 [蓝桥杯 2024 省 Python B] 蓝桥村的真相

在风景如画的蓝桥村，$n$ 名村民围坐在一张古老的圆桌旁，参与一场思想 的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。 当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为 $i$ 的村民提出了这样的断言：坐在他之后的两位村民——也就是 编号 $i + 1$ 和 $i + 2$（注意，编号是环形的，所以如果 $i$ 是最后一个，则 $i + 1$ 是 第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。 在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？ 请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中， 说谎者的总数。

输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。 接下来依次描述 $T$ 组数据。 每个数据一行包含一个整数 $n$，表示村落的人数。

输出 $T$ 行，每行包含一个整数，依次表示每组数据的答案。

对于 $10\%$ 的评测用例，$T = 1，3 \le n \le 10$。 对于 $40\%$ 的评测用例，$1 \le T \le 10^2，3 \le n \le 3 \times10^3$。 对于所有评测用例，$1 \le T \le 10^5，3 \le n \le 10^{18}$。 #### 样例解释 在样例中，可能的组合有「假，假，假」「真，真，假」「真，假，真」「假， 真，真」，说谎者的总数为 $3 + 1 + 1 + 1 = 6$。