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
vis = [[False,False] for i in range(0, 10010)]
ans = [[0,0] for i in range(0, 10010)]
def calc(n, prev):
	if n == 0:
		return 1
	if vis[n][prev]:
		return ans[n][prev]
	x = 0
	vis[n][prev] = True
	if prev == 1:
		x = x + calc(n - 1, 0) + calc(n - 1, 1)
	else:
		x = x + calc(n - 1, 1)
	ans[n][prev] = x
	return ans[n][prev]
t = int(raw_input())
ans[0][0] = 1
ans[0][1] = 1
for i in range(1, 10010):
	ans[i][0] = ans[i-1][1]
	ans[i][1] = ans[i-1][0] + ans[i-1][1]
while t > 0:
	t -= 1
	n = int(raw_input())
	print ans[n][1]