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
<p> </p> <p style="margin: 0cm 0cm 0pt;"><span style="font-size: medium;"><span style="font-family: Simsun;"><span lang="EN-US"><span style="mso-tab-count: 1;">       </span></span></span><span style="font-family: 宋体;">对第一种情况,仅有</span><span style="font-family: Simsun;"><span lang="EN-US" style="mso-fareast-font-family: 'Liberation Serif'; mso-bidi-font-family: 'Liberation Serif';">“</span><span lang="EN-US">1 1 1 1”</span></span><span style="font-family: 宋体;">这一种可能。</span></span></p> <p> </p> <p style="margin: 0cm 0cm 0pt;"><span style="font-size: medium;"><span style="font-family: Simsun;"><span lang="EN-US"><span style="mso-tab-count: 1;">       </span></span></span><span style="font-family: 宋体;">对第二种情况,有</span><span style="font-family: Simsun;"><span lang="EN-US" style="mso-fareast-font-family: 'Liberation Serif'; mso-bidi-font-family: 'Liberation Serif';">“</span><span lang="EN-US">2 1 1 1”“1 1 1 2”</span></span><span style="font-family: 宋体;">两种可能。</span></span></p> <p style="margin: 0cm 0cm 0pt;"> </p> <p style="margin: 0cm 0cm 0pt;"><span style="font-size: medium;"><span style="font-family: 宋体;">输出结果可能超出int范围,请使用longlong长整型。</span></span></p> <p> </p>
source
songwenhao
Submit