题目背景

从 1 数到 10，普通人大概要 3 秒；从 1 数到 100，大概要 30 秒；从 1 数到 10 亿，不吃不喝也要几十年。

但电脑一秒钟大约能做 1 亿（$10^8$）次简单运算。所以，如果一个程序要循环 $n$ 次：

这只是粗略估算，实际速度会受 CPU、编译器和运算类型影响；但用来判断数量级已经足够。时间复杂度不关心具体秒数和常数系数，只关心 $n$ 很大时运算次数怎么增长：

• $O(n)$：大约循环 $n$ 次。$n$ 变成原来的 10 倍，时间也大约变成 10 倍。
• $O(1)$：不管 $n$ 多大，都只做固定几次运算。$n$ 从 10 变成 10 亿，时间几乎不变。

这道题有 $T$ 组询问。如果每组都循环 $n$ 次，总运算量是 $T \times n$；而用公式，每组只要一次乘法，总共只要 $O(T)$。

本题 $n$ 最大 40000，单组循环看起来不多；但 $T$ 最大 $3\times 10^5$，乘起来就是 $3\times 10^5 \times 40000 = 1.2\times 10^{10}$ 次循环。

题目描述

小D制定了 $T$ 个存钱计划。

每个计划的存钱规律都一样：

• 第 1 天，存入 1 元；
• 从第 2 天开始，每天都比前一天多存 2 元。

也就是说，每天存入的钱依次是：

1, 3, 5, 7, 9, ...

第 $i$ 个计划一共存 $n_i$ 天。请你分别算出每个计划结束后，存钱罐里一共有多少元。

输入格式

第一行一个正整数 $T$，表示存钱计划的数量。

接下来 $T$ 行，每行一个正整数 $n_i$，表示第 $i$ 个计划存钱的天数。

输出格式

输出 $T$ 行，每行一个整数，表示对应计划结束后存钱罐里的总钱数。

数据范围

• $1 \le T \le 3\times 10^5$
• $1 \le n_i \le 40000$
• 保证每个计划的答案不超过 $1.6\times 10^9$。

样例

2
1
2

1
4

样例说明

• 样例 ：两个计划分别存 1 天，2 天，答案是 1、4。

提示

$T$ 最大为 $3\times 10^5$，输入输出行数较多，建议使用较快的输入输出方式，例如关闭 cin/cout 同步，或者使用 scanf/printf。