310413: CF1829G. Hits Different

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:10 Solved:0

Description

G. Hits Differenttime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

In a carnival game, there is a huge pyramid of cans with $2023$ rows, numbered in a regular pattern as shown.

If can $9^2$ is hit initially, then all cans colored red in the picture above would fall.

You throw a ball at the pyramid, and it hits a single can with number $n^2$. This causes all cans that are stacked on top of this can to fall (that is, can $n^2$ falls, then the cans directly above $n^2$ fall, then the cans directly above those cans, and so on). For example, the picture above shows the cans that would fall if can $9^2$ is hit.

What is the sum of the numbers on all cans that fall? Recall that $n^2 = n \times n$.

Input

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($1 \leq n \leq 10^6$) — it means that the can you hit has label $n^2$.

Output

For each test case, output a single integer — the sum of the numbers on all cans that fall.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). For all valid inputs, the answer will always fit into 64-bit integer type.

ExampleInput
10
9
1
2
3
4
5
6
10
1434
1000000
Output
156
1
5
10
21
39
46
146
63145186
58116199242129511
Note

The first test case is pictured in the statement. The sum of the numbers that fall is $$1^2 + 2^2 + 3^2 + 5^2 + 6^2 + 9^2 = 1 + 4 + 9 + 25 + 36 + 81 = 156.$$

In the second test case, only the can labeled $1^2$ falls, so the answer is $1^2=1$.

In the third test case, the cans labeled $1^2$ and $2^2$ fall, so the answer is $1^2+2^2=1+4=5$.

In the fourth test case, the cans labeled $1^2$ and $3^2$ fall, so the answer is $1^2+3^2=1+9=10$.

In the fifth test case, the cans labeled $1^2$, $2^2$, and $4^2$ fall, so the answer is $1^2+2^2+4^2=1+4+16=21$.

Input

题意翻译

如上图的纸杯,若一个纸杯倒下,可以得到对应的权值,同时会使得其上方相邻的两个纸杯倒下。求让纸杯 $n$(对应权值为 $n^2$)倒下可以得到的总权值。 Translated by @[_JYqwq_](/user/400269)

Output

题目大意:
在一个嘉年华游戏中,有一个由2023行易拉罐组成的巨大金字塔,按常规模式编号。当你投掷一个球击中金字塔上的一个罐子,标号为n^2,这会导致所有堆在这个罐子上的罐子倒下。求倒下罐子上的数字总和。

输入数据格式:
第一行包含一个整数t(1≤t≤1000)——测试用例的数量。
每个测试用例只有一行,包含一个整数n(1≤n≤10^6)——这意味着你击中的罐子标签为n^2。

输出数据格式:
对于每个测试用例,输出一个整数——所有倒下罐子上的数字总和。

注意:一些测试用例的答案不适合32位整数类型,因此你应在编程语言中使用至少64位整数类型。对于所有有效输入,答案将始终适合64位整数类型。

示例输入输出见题目描述。题目大意: 在一个嘉年华游戏中,有一个由2023行易拉罐组成的巨大金字塔,按常规模式编号。当你投掷一个球击中金字塔上的一个罐子,标号为n^2,这会导致所有堆在这个罐子上的罐子倒下。求倒下罐子上的数字总和。 输入数据格式: 第一行包含一个整数t(1≤t≤1000)——测试用例的数量。 每个测试用例只有一行,包含一个整数n(1≤n≤10^6)——这意味着你击中的罐子标签为n^2。 输出数据格式: 对于每个测试用例,输出一个整数——所有倒下罐子上的数字总和。 注意:一些测试用例的答案不适合32位整数类型,因此你应在编程语言中使用至少64位整数类型。对于所有有效输入,答案将始终适合64位整数类型。 示例输入输出见题目描述。

加入题单

上一题 下一题 算法标签: