Codeforces Round 867 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Bun Lover

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTema loves cinnabon rolls — buns with cinnabon and chocolate in the shape of a "snail".

Cinnabon rolls come in different sizes and are square when viewed from above. The most delicious part of a roll is the chocolate, which is poured in a thin layer over the cinnabon roll in the form of a spiral and around the bun, as in the following picture:

Cinnabon rolls of sizes 4, 5, 6

For a cinnabon roll of size $$$n$$$, the length of the outer side of the square is $$$n$$$, and the length of the shortest vertical chocolate segment in the central part is one.

Formally, the bun consists of two dough spirals separated by chocolate. A cinnabon roll of size $$$n + 1$$$ is obtained from a cinnabon roll of size $$$n$$$ by wrapping each of the dough spirals around the cinnabon roll for another layer.

It is important that a cinnabon roll of size $$$n$$$ is defined in a unique way.

Tema is interested in how much chocolate is in his cinnabon roll of size $$$n$$$. Since Tema has long stopped buying small cinnabon rolls, it is guaranteed that $$$n \ge 4$$$.

Answer this non-obvious question by calculating the total length of the chocolate layer.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The following $$$t$$$ lines describe the test cases.

Each test case is described by a single integer $$$n$$$ ($$$4 \le n \le 10^9$$$) — the size of the cinnabon roll.

Output

Output $$$t$$$ integers. The $$$i$$$-th of them should be equal to the total length of the chocolate layer in the $$$i$$$-th test case.

Example

Input

4456179179179

Output

26 37 50 32105178545472401

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:28:43 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|