Задачи
Остались только веточки...
Остались только веточки...
Миша использовал все шишечки для посадки в лесу новых ёлок и у него для игр с Машей остались только веточки. Естественно, что за зиму они засохли, а так как ещё и были аккуратно сложены, то ещё и все выровнялись. Как-то Маша, наводя порядок в доме, обнаружила эти аккуратно сложенные веточки, больше уже похожие на палочки, и радостно прибежала к Мише:
- \textit{Слушай, Миша! Я нашла наши игрушки - давай поиграем!}
Так как Мишка спешил на прогулку, он ляпнул первое, что ему взбрело в голову:
- \textit{Ты сначала скажи, Маша, сколько разных треугольничков ты можешь построить из этих веточек?} - и увидев удивлённые глаза Маши, с хитрецой дальше проворчал - \textit{А то мне надоело уже помогать тебе с математикой... Да, и не забудь, что использовать ты можешь каждый раз только }\textit{\textbf{3}}\textit{ из всех найденных тобой.} - окончательно озадачил маленькую девочку старый медведь.
Довольный Мишка быстро ушёл в лес на прогулку, а Маша надолго задумалась. Первым делом она измерила длину всех веточек и ещё с большим удивлениям выяснила, что все они имеют разную длину, причем наименьшая имеет длину \textbf{1} см. Попробовав веточки отсортировать по возрастанию длины она выяснила ещё одну закономерность: каждая следуящая веточка также ровно на \textbf{1} см длиннее предыдущей.
- \textit{Да, что-то тут однозначно не так}, - подумала Маша и, уже хорошо выучив все хитрости мудрого медведя, принялась экспериментировать в построении треугольников.
Помогите Маше решить эту задачку к возвращению Миши.
\InputFile
Первая строка каждого теста содержит количество тестовых случаев \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ 1000). В каждой из последующих \textbf{T }строк содержится одно единственное число - количество обнаруженных Машей веточек \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{1000000}).
\OutputFile
Для каждого тестового случая в отдельной строке выведите одно число - ответ к задаче.
Входные данные #1
3 3 4 10
Выходные данные #1
0 1 50