Ожерелья из бусинок

Бусинки красного, синего и зеленого цвета собраны вместе и образуют циклическое ожерелье из n (0 < n < 40) бусинок. Если пренебречь повторениями, полученными в результате поворота вокруг центра и отражениями относительно осей симметрии, сколько различных ожерелий можно образовать?

Входные данные

Каждая строка является отдельным тестом и содержит значение n (0 < n < 40). n = -1 означает конец входных данных.

Выходные данные

Для каждого теста вывести в отдельной строке количество различных ожерелий.

Примеры