1698 - 电影院

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 22

Solved: 6

Description

 


LLY去看电影啦!


 


LLY只买了一张票!


 


LLY一个人入场啦!


 


LLY疯狂吃狗粮


 


       已知电影院的座位通常分为四个区域。现在,单身狗保护会研究决定,设计一种电影院的布局,以保证每排中间区域至少会有一位像LLY这样的单身狗。


 


       单身狗保护协会请你帮助规划电影院的座位布局。座位布局需要满足下述两个条件:


 


       1.座位分为A, B, C, D四个区域,且每个区域的座位数不能为零。


 


       2.中间区域(B&C)的座位数必须为奇数,以保证每排至少有两个像LLY这样的单身狗(微笑)。


 


       你需要知道一共有多少种不同的座位规划方式。两种布局被认定为不同,当且仅当它们A, B, C, D的座位数不全对应相等。


 


 


 

Input

 


       第一行为样例组数T(T<=10000)


 


       接下来每行有一个整数n,代表一排的座位数。(4<=n<=1000000)


 

Output

 


       对每个n首先输出“Case #i: ”(不包含引号,冒号后有一个空格),其中i对应它为第几组数据。输出它对应的规划方式数k


 


 

sample input
2
4
5
sample output
Case #1: 1
Case #2: 2
hint

 

       对第一种情况,仅有1 1 1 1”这一种可能。

 

       对第二种情况,有2 1 1 1”“1 1 1 2”两种可能。

 

输出结果可能超出int范围,请使用longlong长整型。

 

source
songwenhao
© 2015 HUST ACMICPC TEAM. All Right Reserved.