The BITians are furious  that  their  lift  stops working  frequently .Adding  to  this, there  are 7 floors  in BIT  which becomes  really  tedious  to climb.  Vikas has to attend the class in 5th floor. He decides to take a step of 1 or 2 each time to reach his class. He wants to find the number of ways in which he can reach. He is in a hurry, that he will be late to class. He needs your help to solve the problem
There are N stairs to reach the 5th floor. He is at the bottom and wants to reach the top. He can climb either 1 step or 2 steps at a time. Count  the  number  of  ways  in  which  he  can  reach the top.

Input Format:

First line consists T, the number of test cases.
Following  T lines contains the total number of steps to reach the  top.

Output Format:

T lines indicating the number of ways to reach the top.

Constraints: 

1 ≤ T ≤ 105
1 ≤N ≤ 106

SAMPLE INPUT
2
2
4

SAMPLE OUTPUT
2
5
import math
f=math.factorial
t=int(input())

while t>0:
	n=int(raw_input())
	c=0;

	for i in range (0, n+1):
		for j in range (0, n+1):
			if ((1*i)+(2*j))==n:
				c+=f(i+j)/(f(i)*f(j))
	
	print c
	t-=1