Fibonacci lớn

An và Bình chơi với nhau rất thân và cùng có chung niềm đam mê với các dãy số, đặc biệt là dãy số Fibonacci. Một lần An viết ra giấy một dãy số nguyên dương $a_1,a_2,\dots ,a_n$ và muốn Bình hãy đưa ra dãy Fibonacci $F_{a_1},F_{a_2},\dots ,F_{a_n}$. Trong đó dãy Fibonacci được định nghĩa như sau:

• $F_1=1$, $F_2=1$, $F_3=F_1+F_2$;
• $\dots$
• $F_n=F_{n-2}+F_{n-1}$.

Các số $F_{a_i}$ có thể rất lớn, cần in ra chính xác toàn bộ các chữ số.

Yêu cầu: Hãy viết chương trình giúp Bình tính các số Fibonacci theo yêu cầu trên.

Dữ liệu vào

Dữ liệu vào gồm nhiều dòng (số dòng $n$ không được cho trước, đọc đến hết dữ liệu), dòng thứ $i$ chứa số nguyên dương $a_i$ ($a_i\le 1000$; $n\le {10}^6$).

Dữ liệu ra

In ra $n$ dòng, dòng thứ $i$ chứa số $F_{a_i}$.

Ràng buộc

• $1\le n\le {10}^6$.
• $1\le a_i\le 1000$.
• Tổng số chữ số của tất cả các số $F_{a_i}$ cần in không vượt quá $2·{10}^7$.

Ví dụ