Ant and the beanstalk
Time Limit: 0.5 sec
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 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).
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.
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