Little Raju recently learnt about binary numbers. After spending some time with it, he decided to count in how many ways he can make N digit numbers that is formed by ones and zeroes. But zeroes can not be next to each other. Help him finding in how many different numbers can he make?

Example: There 5  possible ways of making different numbers using 3 digit numbers i.e. 101,010,111,110,011

Input

First line of input contains the total number of test cases T.
Next T lines contain N as explained above.

Output

For each test case print  in newline as explained above.

Constraints

1 ≤ t ≤ 10
1 ≤ n ≤ 10^4

SAMPLE INPUT
2
3
7

SAMPLE OUTPUT
5
34
dp={}

def init(n):
	dp[0]=1
	dp[1]=2
	for x in range(2,n+1):
		dp[x]=dp[x-1]+dp[x-2]
#def init(n):
#	if (n<0):
#		return 0
#	if (n==0):
#		return 1
#	if (n==1):
#		return 2
#	if (n in dp):
#		return dp[n]
#	dp[n]=init(n-1)+init(n-2)
#	return dp[n]

init(10000)
t=input()
while t:
	t-=1
	n=input()
	print dp[n]