Migrated from Lutece 592 Jeremy Lin

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Jeremy Lin Graduated from harvard, so everyone thinks he is very clever,but not include Fields, although they are good frinds. so he raise a question to ask Lin crazy to solve,lin is very busy, and you are his fan, so he hope you to help him solve this problem from his best frend.But Fields occur to know this secret and know you are the student of School of Computing. So he demand you writing a program to solve his problem, if you can't finish the task, Fields will charge to Jeremy Lin for the sofa in his room; the problem is Fields has many basketballs,he wants to put them into some plastic bags, but every bags can cotain at most two basketball, now he wants to know how many ways he put those basketball into bags, assume that every basketball is same ,bags is enough and different each other, so if you have $5$ basketball, the way $2, 2, 1$, is not same to the way $2, 1, 2$, everytime you only can take the number of bags you want, int this case, you only can take three, in order to simplified the problem, do not consider the permutation and combination.

Input

first line only a integer $m$ inditcat the case to test( $1 \leq m < 1002$ ),next $m$ lines contain a integer $n$ each line,inditcate the number of basketballs( $0 \leq n < 1001$ )Fields has.

Output

for every test, please give the number of methods mod by $2012$.In order to let Fields see clearly, yuo must give the answer like this Case #num1: num2, num1 represent the Case, num2 represent the number of methods, Each answer take charge of one line.

Samples

5
1
2
3
4
0

Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 5
Case #5: 0

Note

In the fourth Case, there are five ways : 1 1 1 1, 1 1 2, 1 2 1, 2 1 1, 2 2.

Resources

Sichuan University Programming Contest