Triangle Pizza

Time limit1sMemory limit128 MB

Summary

Count the number of distinct connected polyiamonds with N cells, where shapes that match under rotation or translation count as one and reflections are distinct.

Level: Hard8 of 10
Topics: Backtracking, Implementation, Geometry, Brute force
Solved: No attempts yet

Problem

A pizzeria has launched a "triangle pizza" whose every slice is shaped like an equilateral triangle.

A triangle pizza is built from equilateral triangular slices that are all the same size and are joined into a single connected piece. Two slices are considered directly connected when they share an edge.

Write a program that counts the number of distinct shapes a triangle pizza made of exactly $N$ slices can take.

Two shapes are considered the same if one can be rotated and translated so that it exactly overlaps the other. (Flipping the shape over is not allowed.)

Input

The first line contains the number of test cases $T$ .

Each test case consists of a single line containing $N$ , the number of slices in the triangle pizza. ( $1 \le N \le 16$ )

Output

For each test case, print one line in the format Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of distinct triangle-pizza shapes that can be formed from $N$ slices.

Examples4

Example 1

Input

Expected output

Case #1: 1
Case #2: 4
Case #3: 866

Example 2
Input
```
1
1
```
Expected output
```
Case #1: 1
```
Example 3
Input
```
1
3
```
Expected output
```
Case #1: 1
```
Example 4
Input
```
1
5
```
Expected output
```
Case #1: 6
```