구슬 목걸이

시간 제한1초메모리 제한128 MB

요약

회전하거나 뒤집어 겹치는 경우를 하나로 쳐 세 가지 색 구슬 n개로 만들 수 있는 서로 다른 원형 목걸이 수를 각 입력마다 구합니다.

문제

빨강, 파랑, 초록 중 한 가지 색으로 칠한 구슬 $n$ 개를 원형으로 이어 목걸이를 만든다. 목걸이의 중심을 기준으로 돌리거나 대칭축을 기준으로 뒤집었을 때 서로 포개지는 목걸이는 같은 목걸이로 센다.

서로 다른 목걸이가 몇 가지인지 구하라.

입력은 여러 줄로 이루어진다. 각 줄에 구슬의 개수 $n$ 이 하나씩 주어진다 ( $1 \le n \le 23$ ).

$-1$ 이 적힌 줄이 나오면 입력이 끝난다. 이 줄은 처리하지 않는다.

$-1$ 이 나오기 전까지 주어진 각 $n$ 에 대해 서로 다른 목걸이의 개수를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.