Підрахунок чотирикутників
На сітці 10x10 на рисунку, наведеному нижче, Ви можете побачити п'ять різних типів чотирикутників. (Четирикутник у сітці це чотирикутник, вершини якого мають цілочисельні координати, сторони не перетинаються ніде, крім як у вершинах і жоден з внутрішніх кутів не може бути рівним 180 градусів) Звичайно, зображено лише декілька чотирикутників з декількох міліонів, які можна зобразити на цій сітці 10x10. Для заданої сітки NxN Ви повинні визначити загальну кількість чотирикутників, які можуть бути на ній побудовані.
Вхідні дані
Вхідні дані містять не більше 150 тестових прикладів. У кожному рядку міститься єдине число N (0 < N < 121). Вхідні дані завершуються рядком зі значенням N рівним нулю.
Вихідні дані
Для кожного рядка, отриманого на вході, виведіть відповідь у окремому рядку. Кожен рядок повинен містити два числа. Першим числом виведіть число N, отримане із вхідних даних, другим - виведіть кількість шуканих чотирикутників для сітки NxN. Гарантується, що шукане число не перевищуєт 64-бітне ціле число.
Попередження: Ця задача не має альтернативного авторському розв'язку. Для перевірки тестових прикладів можна написати повноперебірний розв'язок. Таким чином Ви зможете знайти всі відповіді для сіток невеликих розмірів (до 22x22), якщо запустите програму на вконання і це займ у Вас біля 14 годин.
Порада: Для системи час на тестування цієї задачі становить 2 секунди. Попередній підрахунок може бути кращим варіантом у випадку, якщо Вам важко знайти ефективний алгоритм розв'язання задачі. Про всяк випадок повідомляємо, що розв'язок, який базується на методі "грубої сили" буде працювати біля 200 років на комп'ютері типу 1.8 Ghz Pentium IV.