자물쇠의 개수

어느 공장에서 스프링 자물쇠를 만든다. 자물쇠 하나에는 홈이 $n$개 있고 ($1 < n < 17$, $n$은 자연수), 각 홈의 높이는 1, 2, 3, 4 중 하나다. 단위는 무시한다.

출고할 수 있는 자물쇠는 다음 두 조건을 모두 만족한다.

• 이웃한 두 홈의 높이 차가 정확히 3인 자리가 적어도 한 곳 있다.
• 홈에 쓰인 높이 값이 적어도 3가지다.

높이 값 4가지를 모두 자유롭게 써서 홈이 $n$개인 자물쇠를 만들 때, 두 조건을 만족하는 자물쇠가 몇 개인지 구하라.

각 줄에 홈의 개수 $n$이 하나씩 주어진다. 마지막 줄에는 -1이 주어지며, 입력이 끝났다는 뜻이다.

입력값마다 자물쇠의 개수를 한 줄씩 출력한다. 줄의 앞부분에 입력받은 $n$을 그대로 쓰고, 콜론과 공백을 붙인 다음, 세어 낸 자물쇠의 개수를 쓴다. 즉 각 줄은 n: 개수 형식이다.