En la ETSINF hay una escalera con \(n\) escalones. Cada vez que subes, puedes avanzar 1 o 2 escalones.
Para varios valores de \(n\), determina de cuántas formas distintas se puede subir la escalera exactamente hasta el último escalón.
Como el número de formas puede ser muy grande, muestra el resultado módulo 10022026.
Entrada
Un entero \(t\), el número de casos de prueba.
En cada caso, un entero no negativo \(n\), que representa el número de escalones.
Se garantiza que no habrá más de \(2 \cdot 10^5\) escalones ni \(2 \cdot 10^5\) casos de prueba.
Salida
Para cada caso, imprime el número de formas de subir la escalera en módulo 10022026.