Підрахунок курей
Курячий фермер Хіоян придбав трьох нових курей: Люсі, Чарлі та ЦЦ. Хіоян хоче збудувати огорожу так, щоб кожна курка мала свій власний безперешкодний вид на околиці. Огорожа повинна мати три сторони, що дозволить кожній курці вільно прогулюватися вздовж своєї сторони, не заважаючи іншим. Хіоян знайшла в сараї рулон дротяної сітки довжиною рівно p футів. Вона хоче визначити кількість способів, якими можна побудувати огорожу для курей так, щоб кожна сторона була цілою і був використаний весь рулон. Огорожі, отримані шляхом обертання, вважаються однаковими, але огорожі, отримані шляхом відображення, можуть бути різними (див. зображення нижче).
Вхідні дані
Перша стрічка містить кількість тестів t (1 ≤ t ≤ 1000). Кожен тест слід обробляти незалежно від інших.
Кожен тест складається з одного рядка, що містить номер тесту та довжину рулону сітки n (3 ≤ n ≤ 10000).
Вихідні дані
Для кожного тесту виведіть в одному рядку номер тесту та загальну кількість різних тристоронніх огорож для курей, які можна збудувати, використовуючи весь рулон.