In Poornima college, PIET CS Deparment is shifting from basement to the third floor. The HOD of the department is trying to finding the number ways to reach the third floor. You are given the number of stairs, and you have to help HOD to find out number of ways in which he can climb the stairs. The HOD is capable of climb maximum two stairs at a time and minimum zero.
Input
The first line contains the number of test cases, T. T lines follow, each of which contains total number of stairs.
Output:
Print the total number of possible ways to climbing the stairs.
Constraints:
1<=T<=100
1<=N<=100
Input: n = 1
Output: 1
There is only one way to climb 1 stair
Input: n = 2
Output: 2
There are two ways: (1, 1) and (2,0)
Input: n = 4
Output: 5
(1, 1, 1, 1), (1, 1, 2,0), (2, 1, 1,0), (1, 2, 1,0), (2, 2,0,0) are the only four ways to climb stairs.
