Tienes una escalera de \(n\) escalones y estás parado en el piso (escalón \(0\)). En cada paso puedes subir 1 escalón o 2 escalones.

Dado \(n\), determina de cuántas maneras distintas puedes llegar desde el piso hasta el escalón \(n\). Dos maneras son distintas si el orden de los pasos es diferente.

Entrada

La primera línea contiene un entero \(t\), el número de casos de prueba.

Cada una de las siguientes \(t\) líneas contiene un entero \(n\), el escalón al que quieres llegar.

Salida

Para cada caso de prueba, imprime en una línea el número de maneras de llegar al escalón \(n\).

Restricciones

• \(1 \le t \le 50\)
• \(1 \le n \le 90\)

Subtareas

Ejemplo

Entrada

3
1
2
4

Salida

1
2
5

Explicación

• Para \(n = 1\) solo hay una forma: \(1\).
• Para \(n = 2\) hay dos formas: \(1+1\) y \(2\).
• Para \(n = 4\) hay cinco formas: \(1+1+1+1\), \(1+1+2\), \(1+2+1\), \(2+1+1\) y \(2+2\).