C. Любитель булочек
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тёма любит синнабоны — булочки с корицей и шоколадом в форме «улитки».

Синнабоны бывают разных размеров и представляют собой квадрат, если смотреть сверху. Самое вкусное в такой булочке — шоколад, который налит тонким слоем поверх синнабона в виде некой спирали и вокруг булочки, как на картинке:

Синнабоны размеров 4, 5, 6

У синнабона размера $$$n$$$ длина внешней стороны квадрата равна $$$n$$$, а длина самого короткого вертикального отрезка шоколада в центральной части равна одному.

Формально, сама булочка состоит из двух спиралей теста, разделенных шоколадом. Синнабон размера $$$n + 1$$$ получается из синнабона размера $$$n$$$ путем оборачивания каждой из спиралей теста вокруг синнабона на ещё один слой.

Важно, что синнабон размера $$$n$$$ определён единственным образом.

Тёме интересно, сколько шоколада содержится в его синнабоне размера $$$n$$$. Так как Тёма давно перестал покупать маленькие синнабоны, то гарантируется, что $$$n \ge 4$$$.

Ответьте на этот неочевидный вопрос, вычислив суммарную длину шоколада на синнабоне.

Входные данные

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных в тесте.

Далее следует $$$t$$$ строк, каждая из которых описывает один набор входных данных.

В единственной строке каждого набора задано целое число $$$n$$$ ($$$4 \le n \le 10^9$$$) — размер синнабона.

Выходные данные

Выведите $$$t$$$ целых чисел, $$$i$$$-е из которых должно быть равно ответу на $$$i$$$-й набор входных данных — суммарной длине слоя шоколада.

Пример
Входные данные
4
4
5
6
179179179
Выходные данные
26
37
50
32105178545472401