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