Tema 喜欢肉桂卷——用肉桂和巧克力制成的“蜗牛”形状的面包。
肉桂卷有不同的尺寸,从上面看呈方形。肉桂卷最美味的部分是巧克力,它以螺旋状薄薄地浇在肉桂卷上,并围绕着小圆面包,如下图:
尺寸为 4、5、6 的肉桂卷
对于尺寸为 $$$n$$$ 的肉桂卷,正方形外侧的长度为 $$$n$$$,中心部分最短的垂直巧克力段的长度为 1。
从形式上来说,小圆面包由两个由巧克力隔开的面团螺旋组成。尺寸为 $$$n + 1$$$ 的肉桂卷是通过将每个面团螺旋缠绕在肉桂卷上另一层而从尺寸为 $$$n$$$ 的肉桂卷获得的。
重要的是,大小为 $$$n$$$ 的肉桂卷以独特的方式定义。
Tema 对他的 $$$n$$$ 肉桂卷中含有多少巧克力感兴趣。由于特马早已停止购买小肉桂卷,因此保证 $$$n \ge 4$$$。
通过计算巧克力层的总长度来回答这个不明显的问题。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
以下 $$$t$$$ 行描述了测试用例。
每个测试用例都由一个整数 $$$n$$$ ($$$4 \le n \le 10^9$$$) 描述 - 肉桂卷的大小。
输出
输出 $$$t$$$ 整数。其中第 $$$i$$$ 应等于第 $$$i$$$ 测试用例中巧克力层的总长度。
示例
输入 #1
4 4 5 6 179179179
输出 #1
26 37 50 32105178545472401