Perfect Squares

A number x is called a perfect square if there exists an integer b
satisfying x=b^2. There are many beautiful theorems about perfect squares in mathematics. Among which, Pythagoras Theorem is the most famous. It says that if the length of three sides of a right triangle is a, b and c respectively(a < b <c), then a^2 + b^2=c^2.
In this problem, we also propose an interesting question about perfect squares. For a given n, we want you to calculate the number of different perfect squares mod 2^n. We call such number f(n) for brevity. For example, when n=2, the sequence of {i^2 mod 2^n} is 0, 1, 0, 1, 0……, so f(2)=2. Since f(n) may be quite large, you only need to output f(n) mod 10007.

The first line contains a number T<=200, which indicates the number of test case.
Then it follows T lines, each line is a positive number n(0<n<2*10^9).

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is f(x).

2
1
2

Case #1: 2
Case #2: 2

2010 ACM-ICPC Multi-University Training Contest（9）——Host by HNU