在风景如画的蓝桥村，n 名村民围坐在一张古老的圆桌旁，参与一场思想的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为 i 的村民提出了这样的断言：坐在他之后的两位村民——也就是编号 i + 1 和 i + 2（注意，编号是环形的，所以如果 i 是最后一个，则 i + 1 是第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？
请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，说谎者的总数。
输入的第一行包含一个整数 T，表示每次输入包含 T 组数据。
接下来依次描述 T 组数据。
每个数据一行包含一个整数 n，表示村落的人数。
2 3 3
6 6
【样例说明】
在样例中，可能的组合有「假，假，假」「真，真，假」「真，假，真」「假，真，真」，说谎者的总数为 3 + 1 + 1 + 1 = 6。
【评测用例规模与约定】
对于 10% 的评测用例，T = 1，3 ≤ n ≤ 10。
对于 40% 的评测用例，1 ≤ T ≤ 102，3 ≤ n ≤ 3 × 103。
对于所有评测用例，1 ≤ T ≤ 105，3 ≤ n ≤ 1018。