题目描述

n个有标号的球围成一个圈。每个球有两种颜色可以选择，黑或白。问有多少种方案使得没有出现连续白球7个或连续黑球7个。

输入格式

有多组数据。第一行T表示组数。(T <= 20)
每组包含n，表示球的个数。(1 <= n <= 100000)

输出格式

每组先输出 "Case #x: " (其中x为当前组数) 该行接下来输出方案数。方案数mod 2015。 

样例数据

input

2
7
1

output

Case #1: 126
Case #2: 2