Necklace of Beads

Time limit1sMemory limit128 MB

Summary

Count distinct circular necklaces of n beads in three colors up to rotation and reflection for each n until -1.

Level: Medium7 of 10
Topics: Combinatorics, Number theory, Math
Solved: No attempts yet

Problem

Beads colored red, blue, or green are strung into a circular necklace of $n$ beads. Two necklaces count as the same one when turning a necklace around the center of the circle, or flipping it over an axis of symmetry, makes it match the other.

Count how many different necklaces there are.

Input

The input has several lines. Each line holds one bead count $n$ ( $1 \le n \le 23$ ).

A line holding $-1$ ends the input, and that line is not processed.

Output

For each $n$ given before $-1$ , print the number of different necklaces on its own line, in the order the values were read.

Examples1

Example 1
Input
```
4
5
-1
```
Expected output
```
21
39
```