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
import sys
f = sys.stdin
DP = [0]*(10001)
for i in range(0,10001):
	DP[i] = [0]*(2)

def pre():
	DP[0][1] = 1 
	for i in range(1,10001):
		DP[i][0] += DP[i-1][1] 
		DP[i][1] += DP[i-1][1]+DP[i-1][0]

T = int(f.readline())
pre() 
while T:
	N = int(f.readline())
	print DP[N][0] + DP[N][1]
	T -= 1