시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 9 8 50.000%

문제

피자햇에서 각 조각이 삼각형 모양인 삼각형 피자를 출시했다.

삼각형 피자는 크기가 같은 정삼각형으로 이루어져 있고, 모든 삼각형은 연결되어져 있다. 두 삼각형이 변을 공유하는 경우에 직접 연결되어있다고 한다.

총 N조각으로 이루어진 삼각형 피자의 서로 다른 모양의 수를 구하는 프로그램을 작성하시오.

한 모양을 회전, 이동 시켜서 다른 모양과 완전히 겹칠 수 있다면, 두 모양은 같은 모양이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 삼각형 피자의 조각의 수 N으로 이루어져 있다. (1 ≤ N ≤ 16)

출력

각 테스트 케이스에 대해서, 가능한 피자 모양의 개수를 출력한다.

예제 입력 1

3
2
4
10

예제 출력 1

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

힌트

W3sicHJvYmxlbV9pZCI6IjYyNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWQ2MTUgXHVkNTNjXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1M2NcdWM3OTBcdWQ1ODdcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWMwYmNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc4IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWQ1M2NcdWM3OTBcdWI5N2MgXHVjZDljXHVjMmRjXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYmNcdWFjMDFcdWQ2MTUgXHVkNTNjXHVjNzkwXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWJjYzBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM5YzFcdWM4MTEgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDFkIE5cdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWQ1M2NcdWM3OTBcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJhYThcdWM1OTFcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHViYWE4XHVjNTkxXHVjNzQ0IFx1ZDY4Y1x1YzgwNCwgXHVjNzc0XHViM2Q5IFx1YzJkY1x1Y2YxY1x1YzExYyBcdWIyZTRcdWI5NzggXHViYWE4XHVjNTkxXHVhY2ZjIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWFjYjlcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHViNDUwIFx1YmFhOFx1YzU5MVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHViYWE4XHVjNTkxXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1ZDUzY1x1Yzc5MFx1Yzc1OCBcdWM4NzBcdWFjMDFcdWM3NTggXHVjMjE4IE5cdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTYpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTNjXHVjNzkwIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyaXBpenphLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg3cHg7IHdpZHRoOjI5N3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2Mjc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWXVtbXkgVHJpYW5ndWxhciBQaXp6YSIsImRlc2NyaXB0aW9uIjoiPHA+UGl6emFoYXQgaGFzIHJlbGVhc2VkIGEgbmV3IHBpenphIHdpdGggdHJpYW5ndWxhciBzaGFwZWQgcGllY2VzLiBUaGlzIHBpenphIGlzIGNvbXBvc2VkIG9mIHNvbWUgZXF1YWwtc2l6ZWQgZXF1aWxhdGVyYWwgdHJpYW5nbGUuIE1vcmVvdmVyLCBhbGwgdGhlIHRyaWFuZ2xlcyBhcmUgY29ubmVjdGVkLiBBbHNvLCBpZiB0d28gdHJpYW5nbGVzIGFyZSBkaXJlY3RseSBjb25uZWN0ZWQsIHRoZXkgbXVzdCBzaGFyZSBhIGNvbW1vbiBlZGdlLjxcL3A+XHJcblxyXG48cD5Ib3cgbWFueSBkaWZmZXJlbnQgc2hhcGVzIG9mIHRoaXMga2luZCBvZiBOLXBpZWNlcyBwaXp6YSBhcmUgdGhlcmU/IFR3byBwYXR0ZXJucyBhcmUgY29uc2lkZXJlZCBhcyBzYW1lIGlmIHRoZXkgY2FuIGNvbXBsZXRlbHkgb3ZlcmxhcCBhZnRlciByb3RhdGlvbiBhbmQgc2hpZnRpbmcgKG5vdGUgdGhhdCBmbGlwcGluZyBpcyBub3QgaW5jbHVkZWQpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgYXJlIG11bHRpcGxlIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZXJlIGlzIG9ubHkgb25lIGxpbmUgd2l0aCBvbmx5IG9uZSBpbnRlZ2VyIE4gZGVub3RpbmcgdGhlIG51bWJlciBvZiBwaWVjZXMgdGhhdCBjYW4gYmUgdXNlZC4gKDEgJmx0Oz0gTiAmbHQ7PSAxNik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcG9zc2libGUgZGlmZmVyZW50IHNoYXBlcyBvZiB0aGUgcGl6emE8XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmlwaXp6YS5wbmdcIiBzdHlsZT1cImhlaWdodDo4N3B4OyB3aWR0aDoyOTdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d