Subes una escalera de \(n\) peldaños y en cada paso avanzas \(1\) o \(2\) peldaños. ¿De cuántas maneras distintas puedes llegar arriba? Dos maneras son distintas si la secuencia de pasos es distinta.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 100)\) y siguen \(T\) líneas con un valor \(n\) \((1 \le n \le 90)\) cada una.

Salida

Para cada \(n\), la cantidad de maneras. (Con \(n = 90\) no cabe en 32 bits, pero sí en un entero de 64 bits.)

Ejemplo 1

Entrada

2
2
3

Salida

2
3

Ejemplo 2

Entrada

1
1

Salida

1

Basado en el problema 70 de LeetCode, Climbing Stairs, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.