TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (18/18)

Submission's AC Ratio

91.2% (31/34)

Description

嗯,聖誕節快到了。

為了要保護美術館裡面的最新展覽品——巨型蕃茄聖誕樹,你決定要布下嚴密的紅外線偵測器。

每一個紅外線偵測器都可以發出兩條紅外線,你可以自由調整這兩條紅外線的發射方向。
由於要嚴防小偷,你自然希望這些紅外線分隔出的區域越多越好(理論上防禦效果較佳)。
假設這個美術館裡面的空間是無限大,而且紅外線可以偵測無限遠,請問你最多可以讓這些紅外線分隔出多少區域呢?

Input Format

輸入檔的第一列有一個正整數T,代表測試資料組數。
接下來有T列,每列有一個正整數n,代表紅外線偵測器的個數($1 \leq n \leq 10^9$)。

Output Format

對於每筆測試資料請輸出一列代表這些紅外線偵測器能夠分隔出的最多區域個數。

Sample Input

2
2
1234

Sample Output

7
3044279

Hints

Problem Source

原TIOJ1158 / 96 TWN Practice Contest 4。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144