题目描述

节日来了，蔓蔓在准备彩灯！

蔓蔓准备了一个树形的彩灯，共有 $n$ 层，第 $i$ 层上有 $2i-1$ 个彩灯。

现在，蔓蔓需要为它们连上电线，使得彩灯可以正常工作。与一般的连法不同，蔓蔓想要让它们看起来像一棵树，于是采用了如下的连线方法：

• 对于第 $i$ 层（$1 \leq i < n$），蔓蔓会把每个彩灯与其下一层最相邻的三个彩灯连上电线；
• 对于第 $n$ 层，蔓蔓会把两两相邻的彩灯连上电线。

蔓蔓已经连好了一个 $n=3$ 的彩灯，如下图所示：

可是，蔓蔓还需要准备 $t$ 个彩灯，但他不想动脑了！于是他找到了你，拜托你帮他连一下电线。你可以帮帮他吗？

输入格式

第一行为一个正整数 $t$，题意如上所述。

接下来 $t$ 行，每行一个正整数 $n$，表示这个彩灯的层数。

对于所有测试数据，满足：$1 \leq t \leq 10^5$，$1 \leq n \leq 10^4$。

输出格式

共 $t$ 行。

每行输出一个整数，表示彩灯需要连多少根电线。

5
1
2
3
4
5

0
5
16
33
56

3
114
514
1919

38533
790533
11040008