Ant and the beanstalk

Time Limit: 0.5 sec

 

The Problem

Ant climbed the beanstalk. He always went upwards. He start from bottom and want to reach top. He can do it different ways.

 

When a beanstalk size is 1 square, he did it like this: left, right. Or he did it like this: right, left. 

So, Ant climbed the beanstalk 2 different ways when beanstalk size is 1 square. 

 

When a beanstalk size are 4 squares, he did it like this: left, right, left, right. Or he did it like this: left, left, right, right. Or he did it like this: left, right, right, left. And so on.

 

Now, your job is to find how many different way the Ant climbed a beanstalk when the size of beanstalk are n squares.

 

The Input

The first line contains a positive integer T ( 0<T<1001), denoting the number of test cases. The next T lines will contain one positive perfect square number n (n<901).

 

The Output

For each test case print "Case X: Y" without quete. Here X denoted the case number and Y denoted the number of different way the Ant climbed to the beanstalk when the size of square is n.

 

Sample Input

3

1

4

36

 

Sample Output

Case 1: 2

Case 2: 6

Case 3: 924

 

 

[Note: In mathematics, a square number or perfect square is an integer that is the square of an integer; First 6 square numbers are 1, 4, 9, 16, 25, 36]

 

Online Practice Contest 3 [School & College Level]

Problem Setter: Shahin ShamS