Lucas numbers X23272

The Lucas numbers $L_0,L_1,L_2,\ldots$ are closely related to the Fibonacci numbers. For any non-negative integer $n\geq 0$, the $n$th Lucas number is defined as $$L_n = \left\{ \begin{array}{ll} 2 & \mathrm{if} \;\; n=0,\\ 1 & \mathrm{if} \;\; n=1,\\ L_{n-1}+L_{n-2} & \mathrm{if} \;\; n>1. \end{array} \right.$$

Input

The input starts with an integer $C$, the number of cases. On each of the following $C$ lines is a single integer $n$ which satisfies $0\leq n\leq 30$.

Output

For each case $n$, output the Lucas number $L_n$ on a single line.