# Bun Lover solution codeforces

Tema 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�+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 n4�≥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 (1t1051≤�≤105) — the number of test cases.

The following t lines describe the test cases.

Each test case is described by a single integer n (4n1094≤�≤109) — 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

26
37
50
32105178545472401