题目描述

某工厂生产一种弹簧锁，每把锁有 $n$ 个槽（$1 < n < 17$，$n$ 为自然数）。每个槽的高度可以是集合 $\{1, 2, 3, 4\}$ 中的任意一个值（忽略单位）。对于一把锁，其槽中至少有一对相邻槽的高度差等于 $3$，并且锁的槽至少有 $3$ 种不同的高度值。如果一批锁的槽高度取遍了上述 $4$ 个值，并且满足上述两个限制条件，求生产的锁的数量。

输入

每行给出一个数据 $n$（槽的数量）。所有输入数据的末尾是 $-1$，表示输入结束。

输出

根据输入数据，计算锁的数量。每个输出占一行，前半部分重复输入数据，然后是一个冒号和一个空格，最后一部分是计算出的锁的数量。

输入样例

2
3
-1

输出样例

2: 0
3: 8

题目来源

西安 2002 年竞赛题目