YUMMY - Yummy Triangular Pizza

Pizzahat has released a new pizza with triangular shaped pieces. This pizza is composed of some equal-sized equilateral triangle. Moreover, all the triangles are connected. Also, if two triangles are directly connected, they must share a common edge.

How many different shapes of this kind of N-pieces pizza are there? Two patterns are considered as same if they can completely overlap after rotation and shifting (note that flipping is not included).

Input

There are multiple test cases. The first line of input contains a single integer denoting the number of test cases.

For each test case, there is only one line with only one integer N denoting the number of pieces that can be used. (1 <= N <= 16)

Output

For each test case, output a single integer denoting the number of possible different shapes of the pizza.

Example

Input:
3
2
4
10

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

This problem is first (and only) solved by team Cabbage (Zhongnan University) at 225 minutes after the onsite contest starts. (They have 1 wrong try before they get Accepted.)


Added by:Fudan University Problem Setters
Date:2011-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM/ICPC Regional Contest, Shanghai 2011; Problem Setter: g201513

hide comments
2024-07-08 11:13:31
hi minh

Last edit: 2024-07-08 11:16:45
2017-07-01 10:39:53
Only Pre-computation!!
2016-04-10 17:09:08
Does shifting here refers to the movement of the triangular pieces?
2015-09-11 09:51:17 loverboy
pre-computation
2014-10-26 10:21:46 Anubhav Balodhi
nice pattern there...
2013-11-29 08:08:25 Sourangsu
Pre-computation is the key...
2013-09-07 10:48:51 pranjuldb
got ac :)... just tried for some cases.. and found the sequence.. !!! :)
2013-03-23 17:13:58 Shubham Sharma
Brings up my half century!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.