Number of Locks

Interview

Time limit1sMemory limit128 MB

Summary

Count length-n strings over heights 1 to 4 that use at least three distinct heights and have an adjacent pair differing by exactly 3.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

A factory makes spring locks. Each lock has $n$ slots ( $1 < n < 17$ , $n$ is a natural number), and the height of every slot is one of 1, 2, 3, 4. Ignore units.

A lock ships only when it meets both conditions below.

At least one pair of neighboring slots has a height difference of exactly 3.
The slots use at least 3 different height values.

Over every way to assign the 4 height values to the $n$ slots, find how many locks meet both conditions.

Input

Each line holds one value $n$ , the number of slots. The last line holds -1, which marks the end of the input.

Output

For each input value, print the number of locks on its own line. Begin the line with the input value $n$ , then a colon and a space, then the counted number of locks, so every line has the form n: count.

Examples1

Example 1
Input
```
2
3
-1
```
Expected output
```
2: 0
3: 8
```