YUMMY  Yummy Triangular Pizza
Pizzahat has released a new pizza with triangular shaped pieces. This pizza is composed of some equalsized 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 Npieces 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.)
hide comments
the_phoenixx:
20170701 10:39:53
Only Precomputation!! 

Anne:
20170111 02:45:47
Last edit: 20170111 02:45:59 

dushyant_bgs:
20160410 17:09:08
Does shifting here refers to the movement of the triangular pieces?


loverboy:
20150911 09:51:17
precomputation 

Anubhav Balodhi :
20141026 10:21:46
nice pattern there... 

Sourangsu :
20131129 08:08:25
Precomputation is the key... 

pranjuldb:
20130907 10:48:51
got ac :)... just tried for some cases.. and found the sequence.. !!! :) 

Shubham Sharma:
20130323 17:13:58
Brings up my half century!!!! 
Added by:  Fudan University Problem Setters 
Date:  20111010 
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 