Залишились лише гілочки...#1300
Лис використав усі шишки, щоб посадити нові троянди на своїй планеті, і для ігор із Маленьким принцом у нього залишилися лише гілочки. Коли минула зима, гілочки висохли, і, оскільки вони були акуратно складені, усі стали прямими. Одного дня, відвідуючи свого друга, Маленький принц знайшов ці акуратно складені гілочки і радісно звернувся до Лиса:
- Послухай, мій друже! Я знайшов ці дивовижні палички — може, погратися з ними?
Але Лис, як завжди мудрий і повний таємниць, промовив перше, що спало йому на думку:
- Спочатку скажи мені, маленький принце, скільки різних трикутників можна скласти з цих гілочок? — і, побачивши здивовані очі свого друга, хитро додав: — Бачиш, найважливіше не видно оком, а лише серцем... Але у математиці теж є свої таємниці. І не забувай, що кожного разу ти можеш використовувати тільки 3 з гілочок, які знайшов. — що остаточно зачарувало Маленького принца.
Так Лис пішов доглядати свої троянди, а Маленький принц залишився міркувати над загадкою. Спочатку він виміряв довжину всіх гілочок і здивувався, коли виявив, що вони всі різної довжини, а найкоротша — 1 см завдовжки. Спробувавши розкласти гілочки у порядку зростання довжини, він знайшов ще одну закономірність: кожна наступна гілочка була рівно на 1 см довша за попередню.
- Так, тут щось точно особливе, — подумав Маленький принц і, пам'ятаючи мудрі уроки Лиса, почав експериментувати зі складанням трикутників.
Допоможіть Маленькому принцу розв'язати цю загадку до повернення Лиса.
У першому рядку кожного тесту міститься кількість тестів (1 \leq T \leq 1000). У наступних рядках міститься одне ціле число — кількість гілочок, які знайшов Маленький принц (3 \leq N \leq 1000000).
Для кожного тесту виведіть єдине число в окремому рядку — відповідь на задачу.
Приклад 1