LLY去看电影啦！

LLY只买了一张票！

LLY一个人入场啦！

LLY疯狂吃狗粮

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

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

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

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

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

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

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

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

2
4
5

Case #1: 1
Case #2: 2

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

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

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