ACM队进新人(二)

Time Limit: 1000MS

Memory Limit: 65535K

Description

今年NJUST ACM队来了n个新人,按照传统,鱼头让他们做了一个游戏。首先,每个人在“A”、“C”、“M”三个字母中选择一个作为他们喜爱的字母。然后,让他们所有人以任意顺序站成一排。鱼头不希望出现这样的情况:从左到右的相邻的三个人,他们喜爱的字母依次是“A”、“C”、“M”。最后,从左到右,把所有人喜爱的字母按次序连接成一个字符串,鱼头想知道总共能组成多少满足条件且互不相同的字符串,这个问题就交给你来解决。

Input

输入由很多组样例组成,每组样例只有一行,包含一个正整数n(3<=n<=40),代表新队员的个数。输入以文件尾结束。

Output

对每一个样例,输出一行,开头是样例的编号(从1开始编号),然后输出能组成字符串的个数。

Sample Input

3
4

Sample Output

Case 1: 26
Case 2: 75

Hint

None

Source

Andfive

提交代码