X was given a maths homework consisting of N problem. The problems are quite hard so X can do atmost 2 problems in a day. He will either solve 1 problem or 2 problems in one day. While X is busy doing the homework, He asks you calculate the number of ways to do N problems.

 INPUT
First line of the input contains an integer T denoting the number of testcases. The description of T testcases is as follows:
Each test case contains only one integer N - denoting the number of no. of problems to solve.

OUTPUT
For each testcase output a single integer denoting the number of ways through which you can solve exactly N problems(no more, no less).

CONSTRAINTS

1<=T<=10^5

1<=N<=80