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:

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 n≥4�≥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≤t≤1051≤�≤105) — the number of test cases.

The following t� lines describe the test cases.

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