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, 6Formally, 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