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