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
memo = [0, 2, 3]
def fib(n):
    i=3
    while i<=n:
    	memo.append(memo[i-1]+memo[i-2])
    	i=i+1

name = raw_input().split("  ")
fib(10005)
nm=int(name[0])
i=1
while i<=nm:
	n = raw_input().split(" ")
	ni=int(n[0])
	print memo[ni]
	i=i+1