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