题目描述

在旺旺家族中，世代相传有一个由若干个相等大小的圆构成的$n$层上正三角。

第$1$层有$1$个圆，第$2$层有$2$个圆，……，第$i$层有$i$个圆，……，第$n$层有$n$个圆。

刚开始，所有圆都是没有颜色的，现在你可以对这个上三角进行若干次染色（可以无数次或零次），但是有限制条件：

• 染色的圆不能相邻
• 不能对一个圆重复染色

请问，最多能染色多少个圆？

输入格式

第一行一个整数 $T（1 \leq T \leq 3 \times 10^5）$ ，表示多组测试样例。

对于每组测试样例：

第一行输入一个正整数 $n（1 \leq n \leq 10^9）$ ,表示上正三角最底层有多少个圆。

输出格式

对于每组测试样例：

输出一个整数 $max$ ，表示对应的上正三角最多能有多少个染色圆。

输入输出样例 #1

输入 #1

5
5
6
1
7
8

输出 #1

6
7
1
10
12

说明/提示

圆的堆叠方式如同超市里堆放的橙子或台球架，形成一个三角网格。以 $n=3$ 为例，结构如下：

     ①
    ② ③
   ④ ⑤ ⑥

相邻定义：如果两个圆在空间上直接接触，即视为相邻。

在此图中：

第 2 层的 ② 与第 1 层的 ①、第 2 层的 ③、以及第 3 层的 ④、⑤ 均相邻。