511006 - 奇异病毒

【题目描述】奇异病毒(virus)

医学研究者发现一种新型病毒“奇异病毒”,它与一长度为N的字符串有关,并满足以下条件: (1) 字符串仅由A,B,C,D四个字母组成; (2) A出现偶数次(也可以不出现); (3) C出现偶数次(也可以不出现)。 例如当N=2时,所有满足条件的字符串有6个:BB,BD,DB,DD,AA,CC。 计算满足条件的字符串个数。

输入

每组输入的第一行是一个整数T(1≤T<100000),表示测试实例的组数。随后是T个整数N(1≤N<2^64),当T=0时结束。

输出

对于每组测试实例,输出字符串个数的最后两位,每组输出后跟一个空行。

样例

输入

4 
1 4 20 11 
3 
14 24 6 
0

Case 1: 56
Case 2: 72
Case 3: 56

输出

Case 1: 2
Case 2: 72
Case 3: 32
Case 4: 0
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题